Problem1090--#2202. 「ZJOI2014」取石子游戏

1090: #2202. 「ZJOI2014」取石子游戏

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

Roland. P Sprague 和 Patrick M. Grundy 都是组合游戏的狂热爱好者,但他们素未谋面。

一天,Sprague 在写给 Grundy 的信中向他介绍了一个据称是来自东方的古老游戏一一取石子。

取石子是一个双人博弈游戏。在游戏的一开始,桌面上有几堆石子堆。接下来,游戏双方轮流进行操作:从桌面上选取一堆石子堆,然后从这一堆里面取走任意多个石子(但不能不取)。当某个人无法操作时则失败,另一方获得胜利。由于条件所限,Sprague 建议在纸上写一排自然数来代表各个石子堆的石子数目,然后两人轮流划数与数;Grundy 欣然应允。

一个月过去了,在 Grundy 连续输了五盘游戏之后,他怀疑 Sprague 要诈。经过几天的研究,Grundy 在某天下午发现假设游戏双方都足够聪明,那么给定一个初始状态(一排自然数),可以有很简单的方法来判定先手必胜还是后手必胜,并且可以给出必胜策略!于是 Grundy 决定要进行反击。

翌日,Grundy 在写给 Sprague 的信中建议把游戏的规则改得更复杂一点:首先确定一个常数 KKK。然后,游戏双方的操作改为:每次选择一个数划掉。假设该数为 xxx,操作者可以任选一个正整数 aaa,在划掉之后需要再写上 x−a,x−2a,…,x−Kax-a,x- 2a,\ldots,x-Kaxa,x2a,,xKaKKK个数,且 aaa 需满足 x−Ka≥0x-Ka \geq 0xKa0。若这样的 aaa 不存在,那么操作者就不能划掉这个 xxx。某一方失败的条件依然是他无法操作。

碍于面子,Sprague 当然无法拒绝。不过他也不会坐以待毙,现在他已经得到了这个 KKK 和写在纸上的 nnn 个数。他把这些数据和这个游戏的规则都告诉了你一一John von Neumann——正在研究如何使用一个尚不存在的机械(你将其命名为计算机)来解决实际问题的数学、物理、经济学(、计算机科学)家。

输入格式

第一行是一个正整数,表示数据组数 TTT (Sprague 向你询问的次数)。
接下来依次输入 TTT 组数据,每组数据占 N+2N+2N+2 行,格式如下:
第一行是一个空行。
第二行,两个正整数,按顺序表示 NNNKKK。 接下来 NNN 行,每行一个正整数,表示写在纸上的 NNN 个数。

输出格式

输出文件共有 TTT 行。
对每组数据,如果先手必胜(先进行操作的玩家拥有必胜策略),则输出 “Preempt.”。若后手必胜,则输出 “Leapfrog.”。若两者皆非,则输出"Je suis un imbecile.”(均含句点 .,不含引号)。

样例

样例输入

2 1 1 1
2 30 197943 249832

样例输出

Preempt.
Leapfrog.

数据范围与提示

10%10\%10% 的数据: N≤5, K=1N \leq 5,\ K=1N5, K=1,所有数均小于等于 555
另有 20%20\%20% 的数据: N≤100, K=1N \leq 100,\ K=1N100, K=1,所有数均小于等于 10910^9109
另有 10%10\%10% 的数据: N≤100, K=2N \leq 100,\ K=2N100, K=2,所有数均小于等于 10910^9109
另有 20%20\%20% 的数据: N≤100, K=2N \leq 100,\ K=2N100, K=2,所有数均小于等于 101810^{18}1018
另有 20%20\%20% 的数据: N≤100, K=10N \leq 100,\ K=10N100, K=10,所有数均小等于 101810^{18}1018
另有 40%40\%40% 的数据: N≤100, K=30N \leq 100,\ K=30N100, K=30,所有数均小等于 108010^{80}1080
100%100\%100% 的数据: T≤10T \leq 10T10

Source/Category