ADAGAME5 - Ada and Palace Game
Ada the Ladybug is celebrating holidays with her good friend Velvet Mite Vinit. They were playing chess all the morning so they have decided to switch games. If you search in your memory (or in SPOJ archive), you'll find out, they invented a new chess-piece: palace. For those, who can't remember the rules of palace (and were not able to find it): The movement of palace is simple - it combines movement of King and Tower.
The game they invented is simple: A few palaces are placed onto chessboard. Ada and Vinit alternate in moves. In each move one can choose any palace on chessboard and move it toward bottom-left corner. Moving closer means, that the Manhattan distance from bottom-left corner will decrease. A player who can't make move will lose. Can you decide the winner?
NOTE: Two palaces can share a chess-field (they will just stack them above each other). Also note that as Ada is a lady she goes first!
Little Warning: The chessboard was a gift from Ada's good friend Flea Feodorv, who is indeed a great programmer yet not as good chess-player, so the bottom-left corner is not traditional "a1" but "[0,0]". Also the upper-right corner is not traditional "h8" but "[2999,2999]".
The first line of input will contain 1 ≤ T ≤ 3*105, the number of test-cases.
The next T lines will contain 1 ≤ N ≤ 3*105, the number of palaces placed on chessboard.
Each test-case will contain N lines containing two integers: 0 ≤ x, y < 3000, the coordinates of palaces.
The sum of N over all test-cases will not exceed 3*105
For each test-case output the name of winner, so either "Ada" or "Vinit".
5 1 3 2 1 3 3 1 6 6 3 7 4 3 7 1 0 5 4 2 6 9 7 8 2 1 5 5
Ada Vinit Vinit Vinit Ada
How do I optimize the Grundy number function?
@sas1905: Good day to you. Nice to hear it actually helped someone. Wish you good holiday too!
After TLE's finally got AC.Learned something new.Merry Christmas..:)
@[Rampage] Blue.Mary: Thank you, fixed
The link to "palace" is wrong. It should be "spoj.com/problems/ADACHES2".
@Michael Kharitonov: Good day to you. Yes, thanx so much! I'll update it!
Ada makes a move first!