#P3618. [Zjoi2014]取石子游戏
[Zjoi2014]取石子游戏
[ZJOI2014] 取石子游戏
题目描述
Roland P. Sprague 和 Patrick M. Grundy 都喜欢组合游戏,却素未谋面。
Sprague 写信给 Grundy,向他介绍据说来自东方的取石子游戏。一开始桌上有若干堆石子。两人轮流选取一堆,取走其中至少一颗石子。轮到某人时如果无法操作,他就输掉游戏。两人没有合适的场地,便在纸上写下一排自然数来表示各堆的石子数,轮流划掉旧数和写下新数。
Grundy 连输五局后,发现可以由初始数列判断谁有必胜策略,并求出这种策略。第二天,他写信建议改变规则。先指定一个常数 ,每次操作时选择纸上的一个数 ,再选择一个正整数 ,满足 。划掉 ,写下以下 个数。
如果对某个 找不到合法的 ,本回合就不能划掉这个数。轮到某人时没有合法操作,此人输掉游戏。
Sprague 接受了新规则。现在他把 和纸上的 个初始数告诉了你。你扮演正在研究如何用计算机解决实际问题的 John von Neumann。求两人都采用最优策略时的结果。
输入格式
第一行一个正整数 ,表示数据组数。每组数据前有一空行。随后一行两个正整数 ,接下来 行每行一个正整数,依次表示纸上的初始数。
输出格式
每组数据输出一行。先手有必胜策略时输出 Preempt.,后手有必胜策略时输出 Leapfrog.,两者都没有必胜策略时输出 Je suis un imbecile.。
样例
2
1 1
1
2 30
197943
249832
Preempt.
Leapfrog.
数据规模与约定
。
| 题源所列数据比例 | 的上限 | 每个初始数的上限 | |
|---|---|---|---|