CF2107B.Apples in Boxes
普及-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Tom 和 Jerry 在地下室中找到了一些苹果,他们决定通过玩一个游戏拿取苹果。
地下室有 n 个箱子,第 i 个箱子里装有 ai 个苹果,Tom 和 Jerry 轮流拿取苹果,从 Tom 开始。当轮到一个人拿取苹果时,他需要:
- 选择一个盒子 i,满足 ai>0,从中拿取一个苹果。这会使得 ai 减小 1。
- 如果没有满足此条件的盒子,当前拿取苹果的玩家输掉。
- 如果在拿取苹果后,max(a1,a2,⋯,an)−min(a1,a2,⋯,an)>k,那么刚刚拿取苹果的玩家输掉。
Tom 和 Jerry 都是理智的,请你推测游戏的结果——谁会获胜?
输入格式
多组数据,第一行一个整数 t(1≤t≤104) 表示数据组数。
对于每组数据:
第一行两个整数 n,k(1≤n≤105,1≤k≤109)。
第二行 n 个整数 a1,a2,⋯,an(1≤ai≤109)。
保证一个测试点中 ∑n≤105。
输出格式
对于每组数据,输出一行,如果 Tom 会赢则输出 Tom,如果 Jerry 会赢则输出 Jerry。
输入输出样例
输入#1
3 3 1 2 1 2 3 1 1 1 3 2 1 1 4
输出#1
Tom Tom Jerry
说明/提示
请注意:以下样例解释中 Tom 和 Jerry 不一定采用了最优策略,以下解释只是在使理解游戏过程变得更方便。
对于第一组数据,一种可能的游戏进行流程如下:
- Tom 选择 i=1,拿取苹果后 a=(1,1,2)。此时 max(1,1,2)−min(1,1,2)=1≤k,所以 Tom 没有输掉。
- Jerry 选择 i=1,拿取苹果后 a=(0,1,2)。此时 max(0,1,2)−min(0,1,2)=2>k,Jerry 输掉了。
By chenxi2009
输入解题思路,AI测评打分。不知道怎么写?