A29215.搭档Nim游戏
普及+/提高
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
Macw, Penelope 和 Vincent 正在玩一个叫做 搭档Nim 的新游戏。游戏在两张桌子上展开,其中一张桌子 (A) 有 N 堆石子,桌子上每一堆石子的个数分别为 A1,A2,⋯AN−1,AN;另一张桌子 (B) 上有 M 堆石子,其中每一堆石子的个数分别为 B1,B2,⋯BM−1,BM。
初始时, Macw 在第 A 桌子上进行游戏, Penelope 在 B 桌子上进行。玩家按照 Vincent, Macw, Penelope 的顺序依次进行操作:
Macw 和 Penelope 遵循传统的 Nim 游戏,在 Macw 的回合,他必须从他所在一桌上选择一堆石子,并从中拿走至少一块石头。在 Penelope 的回合,她也得从她的桌上选一堆石子并拿走至少一块石子。首先无法进行操作的玩家则输掉游戏。
然而,Vincent 不在任何一桌操作,也不参与游戏胜负。在他的回合,他决定 Macw 和 Penelope 是否要交换位置。
Macw 和 Vincent 是伙伴,因此他们的共同目标是让 Macw 获胜。
显然最终 Macw 和 Penelope 中的一人会取得胜利。假设三人都决定的聪明,每个人都采取最优的策略,请你判断游戏最终的获胜者。
Problem credits: Macw07。
输入格式
第一行包含一个整数 T,代表本题的每个测试点一共有 T 组 Testcase。
对于每一个 Testcase:
- 先输入两个整数 N 和 M,表示两张桌子上的石头数量。
- 接下来的一行输入 N 个整数,表示 A1,A2,⋯AN−1,AN。
- 再接下来的一行输入 M 个整数,表示 B1,B2,⋯BM−1,BM。
更具像化的输入如下:
T
Testcase1
Testcase2
⋮
TestcaseT
对于每一个 Testcase:
N M
A1 A2 ⋯ AN−1 AN
B1 B2 ⋯ BB−1 BM
输出格式
对于每组数据,如果 Macw 获胜,则输出 Macw;否则输出 Penelope。每一个 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≤T≤103。
- 1≤N,M≤104。
- 0≤Ai,Bi≤109。
样例解释:
对于第一个 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 失败 |