Moving Pianos
Time limit1sMemory limit128 MB
Each piano job is a day interval; decide whether all jobs fit on weekdays, or only with weekends, or not at all, given p tuners doing floor(p/2) jobs per day.
- Level
Medium6 of 10
- Topics
- Greedy, Intervals, Sorting, Simulation
- Solved
- No attempts yet
Problem
Piano tuners in the city of Hampstead not only tune pianos but also move them, taking turns so that no one carries too much. The following rules apply to every move:
- Tuners always work in pairs; moving one piano requires exactly two tuners.
- No tuner moves more than one piano on any given day.
- Consequently, with tuners at most pianos can be moved per day.
When placing an order you are not told the exact day. Instead, the order for piano is an interval : the piano must be moved on some single day between the beginning of day and the end of day .
Day 1 is always a Monday, day 2 a Tuesday, and so on, so days 6 and 7 are the weekend (Saturday and Sunday); this pattern repeats every week.
For each scenario, decide which of the following holds:
fine— all pianos can be moved using only the five weekdays (Monday–Friday).weekend work— it is impossible on weekdays alone, but possible if the weekend is also used.serious trouble— it is impossible even when all seven days of every week are used.
Input
The first line contains a single positive integer , the number of scenarios.
Each scenario begins with a line containing two positive integers and : is the number of pianos to move, and is the number of tuners.
Then follow lines. The -th line contains two integers and with , meaning piano must be moved between the beginning of day and the end of day .
Output
For each scenario, print exactly one of the following on its own line:
fineif all moves can be carried out during the five weekdays;weekend workif that is impossible and at least two tuners must work on some Saturday or Sunday;serious troubleif the orders cannot be fulfilled as promised even when all tuners work every day.