A3164. 搭档Nim游戏
编程题
普及+/提高
知识点
题目描述
Macw, Penelope 和 Vincent 正在玩一个叫做 $\text{\color{royalblue}{搭档Nim}}$ 的新游戏。游戏在两张桌子上展开，其中一张桌子 (A) 有 $N$ 堆石子，桌子上每一堆石子的个数分别为 $A_1, A_2, \cdots A_{N-1}, A_N$；另一张桌子 (B) 上有 $M$ 堆石子，其中每一堆石子的个数分别为 $B_1, B_2, \cdots B_{M-1}, B_M$。
初始时， Macw 在第 A 桌子上进行游戏， Penelope 在 B 桌子上进行。玩家按照 Vincent, Macw, Penelope 的顺序依次进行操作：
Macw 和 Penelope 遵循传统的 Nim 游戏，在 Macw 的回合，他必须从他所在一桌上选择一堆石子，并从中拿走至少一块石头。在 Penelope 的回合，她也得从她的桌上选一堆石子并拿走至少一块石子。首先无法进行操作的玩家则输掉游戏。
然而，Vincent 不在任何一桌操作，也不参与游戏胜负。在他的回合，他决定 Macw 和 Penelope 是否要交换位置。
Macw 和 Vincent 是伙伴，因此他们的共同目标是让 Macw 获胜。
显然最终 Macw 和 Penelope 中的一人会取得胜利。假设三人都决定的聪明，每个人都采取最优的策略，请你判断游戏最终的获胜者。
Problem credits: [Macw07](https://www.acgo.cn/person/929871)。
初始时， Macw 在第 A 桌子上进行游戏， Penelope 在 B 桌子上进行。玩家按照 Vincent, Macw, Penelope 的顺序依次进行操作：
Macw 和 Penelope 遵循传统的 Nim 游戏，在 Macw 的回合，他必须从他所在一桌上选择一堆石子，并从中拿走至少一块石头。在 Penelope 的回合，她也得从她的桌上选一堆石子并拿走至少一块石子。首先无法进行操作的玩家则输掉游戏。
然而，Vincent 不在任何一桌操作，也不参与游戏胜负。在他的回合，他决定 Macw 和 Penelope 是否要交换位置。
Macw 和 Vincent 是伙伴，因此他们的共同目标是让 Macw 获胜。
显然最终 Macw 和 Penelope 中的一人会取得胜利。假设三人都决定的聪明，每个人都采取最优的策略，请你判断游戏最终的获胜者。
Problem credits: [Macw07](https://www.acgo.cn/person/929871)。
输入格式
第一行包含一个整数 $T$，代表本题的每个测试点一共有 $T$ 组 $\mathtt{Testcase}$。
对于每一个 $\mathtt{Testcase}$：
1. 先输入两个整数 $N$ 和 $M$，表示两张桌子上的石头数量。
2. 接下来的一行输入 $N$ 个整数，表示 $A_1, A_2, \cdots A_{N-1}, A_N$。
3. 再接下来的一行输入 $M$ 个整数，表示 $B_1, B_2, \cdots B_{M-1}, B_M$。
更具像化的输入如下：
> $\mathtt{T}$
> $\mathtt{Testcase_1}$
> $\mathtt{Testcase_2}$
> $\mathtt{\vdots}$
> $\mathtt{Testcase_T}$
对于每一个 $\mathtt{Testcase}$：
> $\mathtt{N\ M}$
> $\mathtt{A_1\ A_2\ \cdots\ A_{N-1}\ A_N}$
> $\mathtt{B_1\ B_2 \ \cdots\ B_{B-1}\ B_M}$
对于每一个 $\mathtt{Testcase}$：
1. 先输入两个整数 $N$ 和 $M$，表示两张桌子上的石头数量。
2. 接下来的一行输入 $N$ 个整数，表示 $A_1, A_2, \cdots A_{N-1}, A_N$。
3. 再接下来的一行输入 $M$ 个整数，表示 $B_1, B_2, \cdots B_{M-1}, B_M$。
更具像化的输入如下：
> $\mathtt{T}$
> $\mathtt{Testcase_1}$
> $\mathtt{Testcase_2}$
> $\mathtt{\vdots}$
> $\mathtt{Testcase_T}$
对于每一个 $\mathtt{Testcase}$：
> $\mathtt{N\ M}$
> $\mathtt{A_1\ A_2\ \cdots\ A_{N-1}\ A_N}$
> $\mathtt{B_1\ B_2 \ \cdots\ B_{B-1}\ B_M}$
输出格式
对于每组数据，如果 Macw 获胜，则输出
Macw；否则输出 Penelope。每一个 $\mathtt{Testcase}$ 之间用一个换行符分隔开。输入输出样例
输入 #1
3 3 1 1 1 1 3 3 1 1 2 4 7 1 1 1 1
输出 #1
Macw Macw Penelope
说明/提示
**数据范围约定：**
对于 $100\%$ 的数据，满足以下要求：
- $1\le T \le 10^3$。
- $1 \le N, M \le 10^4$。
- $0 \le A_i, B_i \le 10^9$。
**样例解释：**
对于第一个 $\mathtt{Testcase}$，一个可行的必胜策略如下:
| 步骤 | A 桌玩家 | A 桌配置 | B 桌玩家 | B 桌配置 | 描述 |
|:---:|:---:|:---:|:---:|:---:|:---:|
| 初始状态 | Macw | $[1, 1, 1]$ | Penelope | $[3]$ | 无|
| Vincent 进行第一轮操作 | Penelope | $[1, 1, 1]$ | Macw | $[3]$ | Vincent 交换了两人的位置 |
| Macw 进行第一轮操作 | Penelope | $[1, 1, 1]$ | Macw | $[0]$ | Macw 一次性拿走三个石子 |
| Penelope 进行第一轮操作 | Penelope | $[0, 1, 1]$ | Macw | $[0]$ | Penelope 拿走了一个石子 |
| Vincent 进行第二轮操作 | Macw | $[0, 1, 1]$ | Penelope | $[0]$ | Vincent 交换了两个人的位置 |
| Macw 进行第二轮操作 | Macw | $[0, 0, 1]$ | Penelope | $[0]$ | Macw 拿走一个石子 |
| Penelope 无法进行任何操作 | Penelope | $[0, 1, 1]$ | Macw | $[0]$ | 由于 Penelope 没有石子可以拿了，因此 Penelope 失败 |
对于 $100\%$ 的数据，满足以下要求：
- $1\le T \le 10^3$。
- $1 \le N, M \le 10^4$。
- $0 \le A_i, B_i \le 10^9$。
**样例解释：**
对于第一个 $\mathtt{Testcase}$，一个可行的必胜策略如下:
| 步骤 | A 桌玩家 | A 桌配置 | B 桌玩家 | B 桌配置 | 描述 |
|:---:|:---:|:---:|:---:|:---:|:---:|
| 初始状态 | Macw | $[1, 1, 1]$ | Penelope | $[3]$ | 无|
| Vincent 进行第一轮操作 | Penelope | $[1, 1, 1]$ | Macw | $[3]$ | Vincent 交换了两人的位置 |
| Macw 进行第一轮操作 | Penelope | $[1, 1, 1]$ | Macw | $[0]$ | Macw 一次性拿走三个石子 |
| Penelope 进行第一轮操作 | Penelope | $[0, 1, 1]$ | Macw | $[0]$ | Penelope 拿走了一个石子 |
| Vincent 进行第二轮操作 | Macw | $[0, 1, 1]$ | Penelope | $[0]$ | Vincent 交换了两个人的位置 |
| Macw 进行第二轮操作 | Macw | $[0, 0, 1]$ | Penelope | $[0]$ | Macw 拿走一个石子 |
| Penelope 无法进行任何操作 | Penelope | $[0, 1, 1]$ | Macw | $[0]$ | 由于 Penelope 没有石子可以拿了，因此 Penelope 失败 |