题意
Ankica 和 Branko 在玩游戏。
有 $n$ 堆石子,第 $i$ 堆有 $a_i$ 个。玩家轮流移除一堆石子中的若干个,取到最后一个石子的玩家获胜。
但在该游戏中每个玩家从哪堆石子中取石子是由另一名玩家固定的。
具体来说,游戏的回合数从 $1$ 开始每次递增,增量为 $1$,而游戏将会以如下方式进行:
- 在奇数回合,Branko 将指定一个非空石子堆。Ankica 将移除这堆石子至少一个。
- 在偶数回合,Ankica 将指定一个非空石子堆。Branko 将移除这堆石子至少一个。
作为专业的游戏玩家,在 Branko 摆完石子后,Ankica 很快意识到这个游戏对她有必胜策略。
你模拟 Ankica,跟交互库对弈。
$1 \leq n \leq 500$
题解
好题,可以先思考一下查看题解
首先,考虑到在游戏仅剩下 石子数量为 $1$ 的石子堆 时,输赢关系仅与这样的石子堆数量有关,而且双方都不可能改变。
这就意味着,Ankica 必须在忽略所有 石子数量为 $1$ 的石子堆 的情况下,用剩下的石子堆操控输赢。
由考虑到,取石子时,要么一次全取走,要么留一颗给对手,否则就把主动权让给了对手,因为 一次全取走 和 留一颗给对手 对应这两种不同的胜负关系,(留一颗给对手 之后可以指定对手取这一堆)。
因此,在至少有一堆 石子数量不为 $1$ 的石子堆 时,Ankica 一定能通过上述方式赢。
如果没有一堆 石子数量不为 $1$ 的石子堆 时,双方都不可能改变结果。而题目保证给出的初始状态使得无论 Branko 怎么操作你都有必胜策略。所以不会出现这种情况。