#P0286. Apples in Boxes

    传统题 1000ms 256MiB 显示标签>Codeforces

Apples in Boxes

题目描述

Tom 和 Jerry 在地下室中找到了一些苹果,他们决定通过玩一个游戏拿取苹果。

地下室有 nn 个箱子,第 ii 个箱子里装有 aia_i 个苹果,Tom 和 Jerry 轮流拿取苹果,从 Tom 开始。当轮到一个人拿取苹果时,他需要:

  • 选择一个盒子 ii,满足 ai>0a_i>0,从中拿取一个苹果。这会使得 aia_i 减小 11
  • 如果没有满足此条件的盒子,当前拿取苹果的玩家输掉。
  • 如果在拿取苹果后,$\max(a_1,a_2,\cdots,a_n)-\min(a_1,a_2,\cdots,a_n)>k$,那么刚刚拿取苹果的玩家输掉。

Tom 和 Jerry 都是理智的,请你推测游戏的结果——谁会获胜?

输入格式

多组数据,第一行一个整数 t(1t104)t(1\le t\le 10^4) 表示数据组数。

对于每组数据:

第一行两个整数 n,k(1n105,1k109)n,k(1\le n\le 10^5,1\le k\le 10^9)
第二行 nn 个整数 a1,a2,,an(1ai109)a_1,a_2,\cdots,a_n(1\le a_i\le 10^9)

保证一个测试点中 n105\sum n\le 10^5

输出格式

对于每组数据,输出一行,如果 Tom 会赢则输出 Tom,如果 Jerry 会赢则输出 Jerry

输入输出样例 #1

输入 #1

3
3 1
2 1 2
3 1
1 1 3
2 1
1 4

输出 #1

Tom
Tom
Jerry

说明/提示

请注意:以下样例解释中 Tom 和 Jerry 不一定采用了最优策略,以下解释只是在使理解游戏过程变得更方便。

对于第一组数据,一种可能的游戏进行流程如下:

  • Tom 选择 i=1i=1,拿取苹果后 a=(1,1,2)a=(1,1,2)。此时 max(1,1,2)min(1,1,2)=1k\max(1,1,2)-\min(1,1,2)=1\le k,所以 Tom 没有输掉。
  • Jerry 选择 i=1i=1,拿取苹果后 a=(0,1,2)a=(0,1,2)。此时 max(0,1,2)min(0,1,2)=2>k\max(0,1,2)-\min(0,1,2)=2> k,Jerry 输掉了。

By chenxi2009