#P14736. [Bulgarian2016春季赛]SandGame

    ID: 13952 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200博弈论区间DP记忆化搜索分治

[Bulgarian2016春季赛]SandGame

题目描述

Eli 和 Kriss 小时候常在楼下沙坑里玩游戏,其中一种游戏规则如下。

首先,她们找来一些普通的 250 毫升塑料杯,每个杯子里装上一些沙子,然后把这些杯子按顺序排成一行。

接着两人轮流操作。轮到某个人时,她需要选择一个杯子,把其中的沙子全部倒入某个相邻的杯子里,然后把原来这个已经空了的杯子丢掉。

规则限制如下:

  • 只有当倒入后目标杯中的沙子总量不超过 250 毫升时,这次操作才合法;
  • 两个杯子必须是严格相邻的。

注意,这里的“相邻”指的是在当前状态下相邻。
例如,若最初有 3 个杯子,第一位玩家把中间杯子倒入左边杯子后,就只剩下原来的最左和最右两个杯子。它们在原始序列中并不相邻,因此接下来另一位玩家不能再在这两个杯子之间进行操作。

迟早会出现这样的局面:当前玩家已经无法把任何一个杯子倒入任何相邻杯子中(要么根本没有相邻杯子,要么相邻杯子太满而无法接收)。此时该玩家判负。

现在 Eli 先手,两人都采用最优策略。请判断谁会获胜。

请编写程序 SandGame

输入格式

第一行输入一个整数 TT,表示游戏局数。

每局游戏包含两行:

  • 第一行一个整数 NN,表示杯子数;
  • 第二行 NN 个整数 AiA_i,表示每个杯子中沙子的体积(单位:毫升)。

输出格式

对每局游戏输出一行:

  • 若 Eli 必胜,输出 Elly
  • 否则输出 Kriss

数据范围

  • 1T101 \le T \le 10
  • 1N1001 \le N \le 100
  • 25Ai25025 \le A_i \le 250

样例

输入

2
3
42 42 42
10
33 42 27 103 175 30 55 202 91 88

输出

Elly
Kriss

样例说明

在第一组测试中,Eli 可以选择中间那个杯子,把它的沙子倒入左边(或者右边)杯子中。这样操作后,Kriss 会处于一个剩余杯子之间不再相邻、因此无法继续操作的局面。