C - Good Strategy
The ACM-ICPC World Finals have begun! However, let's not be too hasty - even though The Team features three of the best coders to have ever coded, they know the importance of first determining what to code.
The contest features N (1 ≤ N ≤ 106) problems (conveniently numbered 1..N), and runs for M (1 ≤ M ≤ 106) minutes. Every problem is associated with a distinct colour - and each time a team solves a problem, they receive a balloon of its corresponding colour, which is visible to all. Obviously, easier problems will be solved by more teams, and so more of their balloons will be floating around in the contest room. Additionally, The Team has found that earlier problems in the set tend to be easier. Therefore, given 2 problems i and j, i is considered easier than j if there are either more i balloons than j balloons in the room, or there are an equal number of balloons and i < j.
At the start of the contest (at the 0th minute), there are no balloons in the room, of course. After that, during every minute i (for i = 1..M), problem pi (1 ≤ pi ≤ N) is either solved by The Team (which will only happen if they have not solved it previously), or by some opposing team. The former possibility is represented by ti = 1, and the latter by ti = 2. In either case, a pi balloon is brought into the room. However, in the former case, The Team will no longer care about problem pi in the slightest.
At the end of every minute after the 0th one, the members of The Team want to get their bearings on what they should be working on (and what they should be staying away from). Specifically, out of problems that they haven't yet solved, they want to know what the single easiest and the single hardest problems are, given the information that can be gleaned from the balloons. These two values may be the same, if The Team has only one problem left to solve. If they're solved all of the problems already, they can instead commence the process of making distracting noises. Are you smart enough to figure out what The Team's strategy throughout the contest will be?
Input
First line: 2 integers, N and M
Next M lines: 2 integers, ti and pi, for i = 1..M
Output
M lines: Either 2 integers, the easiest followed by the hardest unsolved problem number after the first i minutes, or the string "Make noise" if all problems have bee solved by The Team, for i = 1..M.
Sample Input
3 8 2 2 2 1 1 1 2 3 2 3 1 2 1 3 2 1
Sample Output
2 3 1 3 2 3 2 3 3 2 3 3 Make noise Make noise
Explanation of Sample
After the first minute, we've seen 1 balloon for problem 2, and 0 balloons for problems 1 and 3. Therefore, the easiest problem is 2, since it has the most balloons, and the hardest problem is 3, since it's the last problem with the least balloons.
After the second minute, the counts for the 3 problems are 1, 1, and 0. The easiest problem is now 1, since it's the first problem with the most balloons, while the hardest is still 3.
After the third minute, the counts for the 3 problems are 2, 1, and 0, but problem 1 has now been solved by The Team. The easiest remaining problem is 2, and the hardest is 3.
After the fourth minute, the counts for the 3 problems are 2 (solved), 1, and 1. The easiest unsolved problem is 2, and the hardest is 3.
After the fifth minute, the counts for the 3 problems are 2 (solved), 1, and 2. The easiest unsolved problem is 3, and the hardest is 2.
After the sixth minute, the counts for the 3 problems are 2 (solved), 2 (solved), and 2. The only unsolved problem is 3.
After the seventh and eighth minutes, all 3 problems have been solved by The Team, so noise should be made.
All Submissions
Best Solutions
Point Value: 15
Time Limit: 12.00s
Memory Limit: 64M
Added: Jun 01, 2012
Author: SourSpinach
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, TEXT, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
Testcase 1 contains an error: the problem states that a problem will be solved only once by The Team ("which will only happen if they have not solved it previously"). However, in testcase 1 The Team solved the same problem twice.