NAUGHTY - Naughty and Balls
Mr. Naughty likes to play with balls. So his friend, Mr Nice, gave him n balls to play a game. Each ball has exactly two numbers (the number on the top and the number on the bottom). In one move Mr Naughty can rotate any ball so that its bottom now becomes the top. Mr Nice knows the minimum number of such moves that can make at least half of the balls show same number on their top. So to win Mr Nice's game, Mr Naughty should figure out the minimum number of moves. Its not always possible to make such moves that satisfy the given condition.In this case Mr Naughty should figure out that it is "Impossible" to make such moves.
Help Mr Naughty to win the game.
The first line contains a single integer n - the number of balls. The following n lines contain the description of all balls, one ball per line. Each description has a pair of non-negative integers not exceeding 10^5 - numbers on top and bottom. The first number in a line is the number on top, the second one - on the bottom. The number on the top of the ball may be same as the number on the bottom.
The numbers in the lines are separated by single spaces.
On a single line print a single integer - the minimum number of moves to win the game. If it is impossible to make the set funny, print "Impossible" (quotes for clarity).
1 ≤ n ≤ 10^5
3 3 100 100 3 5 4
In this case Mr Naughty can rotate the first ball so that number on the top becomes 100. Since two of the three balls have same number on their top (100), you do not need to change anything else, so the answer is 1.
5 5 9 5 9 3 2 1 4 5 7
3 1 2 3 4 5 6
Problem Setter: Prateek Sachdev
Just brute force .. check for each number
Got sigsiev for 10^5, accepted for 10^6.
Hi Lalit, I don't think your test cases are correct . Not the ones which you have posted, but the ones against which program checks after submission.Last edit: 2014-04-09 08:45:22
Please check my submission I am getting WA again and again ID 11014665Last edit: 2014-02-06 13:17:56
very weak test cases...