CF1842A.Tenzing and Tsondu
入门
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Tsondu always runs first! ! !
Tsondu and Tenzing are playing a card game. Tsondu has n monsters with ability values a1,a2,…,an while Tenzing has m monsters with ability values b1,b2,…,bm.
Tsondu and Tenzing take turns making moves, with Tsondu going first. In each move, the current player chooses two monsters: one on their side and one on the other side. Then, these monsters will fight each other. Suppose the ability values for the chosen monsters are x and y respectively, then the ability values of the monsters will become x−y and y−x respectively. If the ability value of any monster is smaller than or equal to 0, the monster dies.
The game ends when at least one player has no monsters left alive. The winner is the player with at least one monster left alive. If both players have no monsters left alive, the game ends in a draw.
Find the result of the game when both players play optimally.
Tsondu 总是先手!!!
Tsondu 和 Tenzing 正在玩一个卡牌游戏。Tsondu 拥有 n 只怪兽,其能力值分别为 a1,a2,…,an;而 Tenzing 拥有 m 只怪兽,其能力值分别为 b1,b2,…,bm。
Tsondu 和 Tenzing 轮流行动,Tsondu 先手。在每一轮中,当前玩家需选择两只怪兽:一只属于自己一方,另一只属于对方一方。随后,这两只怪兽相互战斗。假设所选怪兽的能力值分别为 x 和 y,则战斗后它们的能力值分别变为 x−y 和 y−x。若某只怪兽的能力值小于或等于 0,则该怪兽死亡。
当至少有一方没有任何存活的怪兽时,游戏结束。获胜者为仍至少拥有一只存活怪兽的玩家。若双方均无存活怪兽,则游戏以平局告终。
求当双方均采取最优策略时,游戏的结果。
输入格式
Each test contains multiple test cases. The first line of input contains a single integer t (1≤t≤2⋅103) — the number of test cases. The description of test cases follows.
The first line of each test case contains two integers n and m (1≤n,m≤50) — the number of monsters Tsondu and Tenzing have respectively.
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109) — the ability values of Tsondu's monsters.
The third line of each test case contains m integers b1,b2,…,bm (1≤bi≤109) — the ability values of Tenzing's monsters.
每个测试包含多个测试用例。输入的第一行是一个整数 t(1≤t≤2⋅103),表示测试用例的数量。随后是各测试用例的描述。
每个测试用例的第一行包含两个整数 n 和 m(1≤n,m≤50),分别表示 Tsondu 和 Tenzing 所拥有的怪物数量。
每个测试用例的第二行包含 n 个整数 a1,a2,…,an(1≤ai≤109),表示 Tsondu 的怪物的能力值。
每个测试用例的第三行包含 m 个整数 b1,b2,…,bm(1≤bi≤109),表示 Tenzing 的怪物的能力值。
输出格式
For each test case, output "Tsondu" if Tsondu wins, "Tenzing" if Tenzing wins, and "Draw" if the game ends in a draw. (Output without quotes.)
Note that the output is case-sensitive. For example, if the answer is "Tsondu", the outputs "tsondu", "TSONDU", and "tSonDu" will all be recognized as incorrect outputs.
对于每个测试用例,如果 Tsondu 获胜,则输出 “Tsondu”;如果 Tenzing 获胜,则输出 “Tenzing”;如果游戏平局,则输出 “Draw”。(输出不带引号。)
注意:输出区分大小写。例如,若答案为 “Tsondu”,则输出 “tsondu”、“TSONDU” 和 “tSonDu” 均会被判为错误输出。
输入输出样例
输入#1
6 1 3 9 1 2 3 2 3 1 2 1 1 1 3 2 1 2 3 1 1 3 3 1 1 1 2 2 2 10 10 1 2 3 3 2 2 1 1 2 2 3 3 3 3 2 1 1 1 1 1 10 10 1 2 3 4 5 6 7 8 9 10 6 7 8 9 10 11 1 1 1 1
输出#1
Tsondu Draw Tsondu Tenzing Draw Draw
说明/提示
Consider the first test case. It can be shown that Tsondu has a winning strategy. The following is a possible way that Tsondu can win (note that the players may not be playing optimally in this example):
- In the first move, Tsondu chooses a monster with ability value 9 on his side to fight against a monster with ability value 1 on Tenzing's side, the ability value of both monsters become 8 and −8 respectively. The monster with ability value −8 on Tenzing's side dies.
- In the second move, Tenzing chooses a monster with ability value 2 on his side to fight against a monster with ability value 8 on Tsondu's side, the ability value of both monsters become −6 and 6 respectively. The monster with ability value −6 on Tenzing's side dies.
- In the third move, Tsondu chooses a monster with ability value 6 on his side to fight against a monster with ability value 3 onTenzing's side, the ability value of both monsters become 3 and −3 respectively. The monster with ability value −3 on Tenzing's side dies.
- Now, Tenzing has no monsters left alive. Since Tsondu still has monsters left alive, Tsondu wins.
考虑第一个测试用例。可以证明,Tsondu 有一个必胜策略。以下是 Tsondu 可能获胜的一种方式(注意:在此示例中,双方玩家未必采取最优策略):
- 第一步:Tsondu 选择己方能力值为 9 的怪物,与 Tenzing 方能力值为 1 的怪物对战,双方怪物的能力值分别变为 8 和 −8;Tenzing 方能力值为 −8 的怪物死亡。
- 第二步:Tenzing 选择己方能力值为 2 的怪物,与 Tsondu 方能力值为 8 的怪物对战,双方怪物的能力值分别变为 −6 和 6;Tenzing 方能力值为 −6 的怪物死亡。
- 第三步:Tsondu 选择己方能力值为 6 的怪物,与 Tenzing 方能力值为 3 的怪物对战,双方怪物的能力值分别变为 3 和 −3;Tenzing 方能力值为 −3 的怪物死亡。
- 此时,Tenzing 已无存活怪物。由于 Tsondu 仍有存活怪物,因此 Tsondu 获胜。
输入解题思路,AI测评打分。不知道怎么写?