Constrained Nim

题目描述

Takahashi 和 Aoki 将使用 $N$ 堆石子互相对战。 最初，对于每个 $i = 1, 2, \ldots, N$，第 $i$ 堆由 $A_i$ 个石子组成。 玩家交替进行以下操作，Takahashi 先手。

选择一堆剩余至少一个石子的堆，并移去一个或多个石子。

但是，有 $M$ 个禁止的移动。
对于每个 $i = 1, 2, \ldots, M$，在恰好由 $X_i$ 个石子组成的堆上移去恰好 $Y_i$ 个石子是不允许的。 第一个无法进行操作的玩家将输，另一位玩家获胜。 当双方都采用最优策略以争取胜利时，哪位玩家将获胜？

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_M$ $Y_M$

输出格式

如果在双方都采用最优策略时 Takahashi 将获胜，输出 $Takahashi$；如果 Aoki 将获胜，输出 $Aoki$。

3 4
1 2 4
2 1
3 3
3 1
1 1

Takahashi

1 5
5
5 1
5 2
5 3
5 4
5 5

Aoki

提示

$1 \leq N \leq 2 \times 10^5$ $1 \leq M \leq 2 \times 10^5$ $1 \leq A_i \leq 10^{18}$ $1 \leq Y_i \leq X_i \leq 10^{18}$ $i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j)$ 输入中的所有值均为整数。对于每个 $i = 1, 2, 3$，令 $A'_i$ 为第 $i$ 堆中剩余的石子数。现在，我们使用序列 $A' = (A'_1, A'_2, A'_3)$ 来表示各堆中剩余的石子数。 比赛开始前，我们有 $A' = (1, 2, 4)$。游戏的一种可能进程如下。

首先，Takahashi 从第 $3$ 堆移去 $1$ 个石子。现在，$A' = (1, 2, 3)$。 接着，Aoki 从第 $2$ 堆移去 $2$ 个石子。现在，$A' = (1, 0, 3)$。 然后，Takahashi 从第 $3$ 堆移去 $2$ 个石子。现在，$A' = (1, 0, 1)$。

此时，第 $1$ 堆和第 $3$ 堆仍各有 $1$ 个石子，但作为第四个禁止的移动，恰在由 $1$ 个石子组成的堆上移去恰好 $1$ 个石子是被禁止的，所以 Aoki 无法走子。因此，Takahashi 获胜。

标签: AtCoder|abc255G

来源

AtCoder|abc255G