#P14736. [Bulgarian2016春季赛]SandGame
[Bulgarian2016春季赛]SandGame
题目描述
Eli 和 Kriss 小时候常在楼下沙坑里玩游戏,其中一种游戏规则如下。
首先,她们找来一些普通的 250 毫升塑料杯,每个杯子里装上一些沙子,然后把这些杯子按顺序排成一行。
接着两人轮流操作。轮到某个人时,她需要选择一个杯子,把其中的沙子全部倒入某个相邻的杯子里,然后把原来这个已经空了的杯子丢掉。
规则限制如下:
- 只有当倒入后目标杯中的沙子总量不超过 250 毫升时,这次操作才合法;
- 两个杯子必须是严格相邻的。
注意,这里的“相邻”指的是在当前状态下相邻。
例如,若最初有 3 个杯子,第一位玩家把中间杯子倒入左边杯子后,就只剩下原来的最左和最右两个杯子。它们在原始序列中并不相邻,因此接下来另一位玩家不能再在这两个杯子之间进行操作。
迟早会出现这样的局面:当前玩家已经无法把任何一个杯子倒入任何相邻杯子中(要么根本没有相邻杯子,要么相邻杯子太满而无法接收)。此时该玩家判负。
现在 Eli 先手,两人都采用最优策略。请判断谁会获胜。
请编写程序 SandGame。
输入格式
第一行输入一个整数 ,表示游戏局数。
每局游戏包含两行:
- 第一行一个整数 ,表示杯子数;
- 第二行 个整数 ,表示每个杯子中沙子的体积(单位:毫升)。
输出格式
对每局游戏输出一行:
- 若 Eli 必胜,输出
Elly; - 否则输出
Kriss。
数据范围
- ;
- ;
- 。
样例
输入
2
3
42 42 42
10
33 42 27 103 175 30 55 202 91 88
输出
Elly
Kriss
样例说明
在第一组测试中,Eli 可以选择中间那个杯子,把它的沙子倒入左边(或者右边)杯子中。这样操作后,Kriss 会处于一个剩余杯子之间不再相邻、因此无法继续操作的局面。