Challenge 15 - Intervals
You love doughnuts very much (yes you do!), so after seeing your friend come to work with a big box of delicious strawberry jam doughnuts you can't help but pester him for some. It turns out, however, that your friend doesn't like doughnuts that much! Instead, he loves intervals.
He has agreed to give you a doughnut if you can beat him in the following turn-based game:
- There are some closed intervals. These are special: an interval can be completely contained inside other intervals, but two intervals will never partially intersect:
- On each turn, a player picks any integer contained in at least one interval, and all the intervals containing this integer disappear
- A player loses if he cannot pick any number on his/her turn (no more intervals left)
Because he is very good at this game, he has decided to let you play first. Can you get some doughnuts?
The first line will contain an integer C, the number of cases for our problem.
Each case consists of a line with an integer N, the number of intervals. A set of N lines with two integers a and b follows.
Each line describes an interval [a, b]
For each case, a line starting with "Case #x: " followed by the minimum integer to pick to win the game or the string IMPOSSIBLE if you can't win (every line is followed by a new line character).
Case 1: 1 2 5
In Case 1, the answer is 2. You can pick 2, 3, 4 or 5.
In Case 2, the answer is IMPOSSIBLE. No matter which number you pick in your first turn your friend will have one interval left on his next turn.
In Case 3, the answer is 2. You can pick 2, 3 or 4 to get rid of both intervals.
In Case 4, the answer is 1. You can pick 1 or 5, leaving your friend with two separate intervals on his next turn.
- 1 ≤ N ≤ 105
- -231 ≤ a < b ≤ 231
4 1 2 5 2 1 3 5 7 2 1 5 2 4 3 1 5 2 4 6 9
Case #1: 2 Case #2: IMPOSSIBLE Case #3: 2 Case #4: 1
Test your code
You can test your program against both the input provided in the test phase and the input provided in the submit phase. A nice output will tell you if your program got the right solution or not. You can try as many times as you want to. Be careful with extra whitespaces, the output should be exactly as described.
Test your program against the input provided in the test phase
Test your program against the input provided in the submit phase
During the submit phase, in some problems, we might give your program harder inputs. As with the test token, a nice output will tell you if your program got the right solution or not. You can try as many times as you need.
In the actual contest you first need to solve the test phase before submitting the code, you must provide the source code used to solve the challenge and you can only submit once (once your solution is submitted you won't be able to amend it to fix issues or make it faster).
If you have any doubts, please check the info section.