Unfair Nim

题目描述

有 $N$ 堆石子。第 $i$ 堆有 $A_i$ 个石子。 Aoki 和 Takahashi 将用它们来玩下述游戏：

从 Aoki 开始，两名玩家交替进行以下操作： 操作：选择一堆石子，并从中移走一个或多个石子。

当某位玩家无法进行操作时，他输，另一位玩家赢。

当两位玩家都最优地玩时，该游戏有两种可能性：先手玩家总是获胜，或后手玩家总是获胜，这仅取决于每堆的初始石子数量。 在这种情况下，作为后手的 Takahashi 试图通过在游戏开始前从第 $1$ 堆向第 $2$ 堆移动至少 $0$ 且至多 $(A_1 - 1)$ 个石子来保证他的胜利。 如果这是可能的，输出为了保证他获胜所需移动的最小石子数；否则输出 $-1$。

输入格式

从标准输入读取，格式如下： $N$ $A_1$ $\ldots$ $A_N$

输出格式

输出为了保证 Takahashi 胜利所需移动的最小石子数；否则输出 $-1$。

2
5 3

1

2
3 5

-1

3
1 1 2

-1

8
10 9 8 7 6 5 4 3

3

3
4294967297 8589934593 12884901890

1

提示

$2 \leq N \leq 300$ $1 \leq A_i \leq 10^{12}$如果不移动石子，若 Aoki 首先从第 $1$ 堆移走 $2$ 个石子，Takahashi 无论如何都无法获胜。 如果 Takahashi 在游戏开始前从第 $1$ 堆向第 $2$ 堆移动 $1$ 个石子，使得两堆各有 $4$ 个石子，Takahashi 通过恰当选择其动作可以始终获胜。
不允许从第 $2$ 堆向第 $1$ 堆移动石子。
不允许将第 $1$ 堆的所有石子都移动走。
注意溢出。

标签: AtCoder|abc172F

来源

AtCoder|abc172F