#P1143. Number Game

    ID: 144 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>动态规划Mid-Central European Regional Contest 2000

Number Game

题目描述(Description)

Christine 和 Matt 发明了一款非常刺激的游戏,名叫 数字游戏(Number Game),他们轮流玩这款游戏,规则如下:

玩家轮流选择大于 11 的整数;

游戏由 Christine 先手,然后 Matt,之后轮流进行;

玩家在选择数字时,必须遵循以下两条限制规则:

禁选规则:

一个数字一旦被选过,或是被选数字的倍数,都不能再选;

若一个数字能被表示为若干已选数字的倍数之和,也不能被选。

示例说明:

Christine 选择了 44,那么 4,8,12,4, 8, 12, \dots 都不能再选;

Matt 选择了 33,那么 3,6,9,3, 6, 9, \dots 也不能再选;

同时,7=3+47 = 3 + 410=23+410 = 2 \cdot 3 + 411=3+2411 = 3 + 2 \cdot 4,这些“已选数的倍数之和”也禁止;

如果最后某个玩家 没有合法可选数字,那他就输了。

任务目标:

编写一个程序,给出当前可以选择的数字集合,判断其中哪些数字是“必赢选项”。

输入格式(Input)

每个测试用例占据一行,格式如下:

n a_1 a_2 \dots a_n nn:当前仍可选的数字个数,1n201 \leq n \leq 20

aia_i:所有还可以选择的数字,满足 2ai202 \leq a_i \leq 20

所给的集合总是合法的(即不会出现如 33 不在,但 66 还在的非法情况);

最后一行为单独的 00,表示输入结束,不用处理。

输出格式(Output)

对于每组测试用例,输出格式如下:

先输出:Test Case #m,其中 mm 是测试用例编号(从 11 开始);

然后判断当前局面是否存在“必赢选项”:

如果没有:输出 There's no winning move.;

如果有:输出 The winning moves are: w_1 w_2 \dots w_k,其中 wiw_i 是升序排列的所有必赢数字;

每组输出之间空一行。

2 2 5
2 2 3
5 2 3 4 5 6
0
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