Number Card Removal Game
Time limit1sMemory limit256 MB
For each N, cards 1..N are played by removing a card x together with x-1 and x+1; find who wins under perfect play.
- Level
Medium7 of 10
- Topics
- Game theory, Dynamic programming, Math, Combinatorics
- Solved
- No attempts yet
Problem
Yuto and Platina are about to play a number card game. The game starts with N number cards, each having a distinct number from 1 to N written on it.
On each turn, a player takes one number card. If the number on that card is x, all number cards whose numbers are x-1, x, or x+1 are removed.
Players take turns, and Yuto always moves first. A player who starts their turn with no number cards remaining loses.
Both play perfectly. They find this game so much fun that they want to play T rounds, changing the number of number cards each time.
Doldol thinks the game will take too long and is bored of watching it, so he wants to predict the results in advance.
For each of the T games, given N, tell him the winner so Doldol can sleep well!
Input
The first line gives a positive integer T, the number of games to play.
Each of the following T lines gives N, the number of number cards used in that game.
Output
Over T lines, print the name of the player who will win each game.
Constraints
- 1 ≤ T ≤ 105
- 1 ≤ N ≤ 5×106