Number Game
Time limit1sMemory limit128 MB
Given the numbers still allowed by previous choices, list every move that leaves the opponent in a losing position, or report that none exists.
- Level
Medium7 of 10
- Topics
- Game theory, Dynamic programming, Brute force, Number theory
- Solved
- No attempts yet
Problem
Christine and Matt play a game they invented, the Number Game. The rules are as follows.
The players alternate turns, each choosing an integer greater than . Christine moves first, then Matt, then Christine, and so on. Every number chosen so far restricts the numbers that may still be chosen:
- A number that either player has already chosen, or any multiple of such a number, may not be chosen.
- Any sum of such multiples may not be chosen either.
In other words, once a set of numbers has been chosen, every non-negative integer combination of them (with at least one positive coefficient) becomes forbidden. A player who cannot choose any new number loses.
Example. Christine starts with , which forbids . Matt answers with , which additionally forbids as well as sums such as , , , , and so on. The only numbers still available are and . Christine now chooses ; since becomes forbidden, no number is left for Matt, so Christine wins.
After enough moves the set of remaining choices becomes finite. Given a position (the list of numbers that are not yet forbidden), output every winning move.
A winning move is a move after which the mover can force a win no matter how the opponent replies. Formally:
- A winning move is a move that leaves the opponent in a losing position.
- A winning position is a position in which a winning move exists; a losing position is a position in which no winning move exists.
- The position in which every number is forbidden is a losing position (the player to move there loses).
Input
The input contains several test cases, one position per line. Each line begins with an integer (), the count of numbers that are still available, followed by those numbers (). Every position given can actually arise in the game (for example, if is not available then is not available either). The input ends with a line containing a single , which must not be processed.
Output
For the -th test case ( starting at ), first print Test Case #m. On the next line print There's no winning move. if the position has no winning move, or The winning moves are: w1 w2 ... wk listing all winning moves in increasing order (). Print one blank line between consecutive test cases.