This page is still under construction.

Parts of this page are still being built. What you see may change.

Number Game

Time limit1sMemory limit128 MB

Summary
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 11. 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 44, which forbids 4,8,12,…4, 8, 12, \dots. Matt answers with 33, which additionally forbids 3,6,9,…3, 6, 9, \dots as well as sums such as 7=3+47 = 3 + 4, 10=2⋅3+410 = 2 \cdot 3 + 4, 11=3+2⋅411 = 3 + 2 \cdot 4, 13=3⋅3+413 = 3 \cdot 3 + 4, and so on. The only numbers still available are 22 and 55. Christine now chooses 22; since 5=2+35 = 2 + 3 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 nn (1≤n≤201 \le n \le 20), the count of numbers that are still available, followed by those nn numbers a1,…,ana_1, \dots, a_n (2≤ai≤202 \le a_i \le 20). Every position given can actually arise in the game (for example, if 33 is not available then 66 is not available either). The input ends with a line containing a single 00, which must not be processed.

Output

For the mm-th test case (mm starting at 11), 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 (wi<wi+1w_i < w_{i+1}). Print one blank line between consecutive test cases.

Examples4

  1. Example 1

    Input
    2 2 5
    2 2 3
    5 2 3 4 5 6
    0
    
    Expected output
    Test Case #1
    The winning moves are: 2
    
    Test Case #2
    There's no winning move.
    
    Test Case #3
    The winning moves are: 4 5 6
    
  2. Example 2

    Input
    1 2
    0
    
    Expected output
    Test Case #1
    The winning moves are: 2
    
  3. Example 3

    Input
    1 3
    0
    
    Expected output
    Test Case #1
    The winning moves are: 3
    
  4. Example 4

    Input
    2 2 3
    0
    
    Expected output
    Test Case #1
    There's no winning move.