AT_abc172_f [ABC172F] Unfair Nim

题目描述

有 $N$ 堆石子，第 $i$ 堆有 $A_i$ 个石子。

青木君和高桥君打算用这些石子玩如下游戏：

• 从青木君开始，轮流进行如下操作：
  • 操作：选择一堆石子，从中取走至少 $1$ 个石子。
• 不能进行操作的一方判负。

在双方都采取最优策略的情况下，游戏的胜负仅由初始每堆石子的数量决定。

高桥君希望在游戏开始前，将第 $1$ 堆中的 $0$ 个以上且少于 $A_1$ 个石子移动到第 $2$ 堆，使得作为后手的高桥君能够必胜。

如果可以做到，请输出需要移动的最小石子数；否则输出 $-1$。

输入格式

输入通过标准输入给出，格式如下：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出需要移动的最小石子数。如果无法做到，则输出 $-1$。

输入输出样例 #1

输入 #1

2
5 3

输出 #1

1

输入输出样例 #2

输入 #2

2
3 5

输出 #2

-1

输入输出样例 #3

输入 #3

3
1 1 2

输出 #3

-1

输入输出样例 #4

输入 #4

8
10 9 8 7 6 5 4 3

输出 #4

3

输入输出样例 #5

输入 #5

3
4294967297 8589934593 12884901890

输出 #5

1

说明/提示

限制条件

• $2 \leq N \leq 300$
• $1 \leq A_i \leq 10^{12}$

样例解释 1

如果不移动石子，青木君可以先从第 $1$ 堆取走 $2$ 个石子，无论高桥君之后如何操作，都会输。如果在游戏开始前从第 $1$ 堆移动 $1$ 个石子到第 $2$ 堆，使得两堆分别为 $4,4$，那么高桥君可以通过合理操作必胜。

样例解释 2

不能将石子从第 $2$ 堆移动到第 $1$ 堆。

样例解释 3

不能将第 $1$ 堆的所有石子都移动走。

样例解释 5

请注意防止溢出。

由 ChatGPT 4.1 翻译