#P17068. [ICPC 2017 Shenyang R] Defense of the Ancients

[ICPC 2017 Shenyang R] Defense of the Ancients

背景

原测试数据丢失,换用了民间测试数据。

题目描述

在《Defense of the Ancients》游戏中,一方队伍拥有 nn 个单位,另一方队伍拥有 mm 座防御塔。每个单位和每座塔都拥有一定的生命值(HP)和固定的攻击力(AP)。生命值为正的单位(或塔)视为存活,可以攻击敌方塔(或单位);生命值为零的单位(或塔)视为阵亡(或被摧毁),无法进行攻击。

游戏是实时进行的,时间连续流逝。若一座塔(或一个单位)同时正受到 kk 个单位(或 kk 座塔)的攻击,且攻击力分别为 a1,a2,,aka_1, a_2, \dots, a_k,则其生命值将以每秒 a1+a2++aka_1 + a_2 + \dots + a_k 的速率持续减少。攻击没有射程限制,即任意单位可以攻击任意塔,反之亦然。

在整个游戏过程中,存活的一方(单位或塔)将会集中火力攻击选定的一个敌方目标,直至将其摧毁(或击杀)。也就是说,存活的单位(或塔)会逐个集火消灭敌方的塔(或单位)。

若所有单位阵亡且至少有一座塔存活,则塔方获胜。若所有塔被摧毁且至少有一个单位存活,则单位方获胜。若所有单位阵亡与所有塔被摧毁同时发生,则游戏以平局结束。

双方均采取最优策略。你的任务是预测游戏的胜者。

输入格式

第一行是一个整数,表示测试用例的数量,最多不超过 1010

对于每个测试用例,共有 55 行。第一行包含两个整数 nnmm0<n1050 < n \le 10^50<m1050 < m \le 10^5)。第二行包含 nn 个整数,表示各个单位的生命值。第三行包含 nn 个整数,表示各个单位的攻击力。第四行包含 mm 个整数,表示各个塔的生命值。第五行包含 mm 个整数,表示各个塔的攻击力。

所有生命值和攻击力均为正整数且小于 2322^{32}

输出格式

对于每个测试用例,若单位方拥有必胜策略,则输出 “Units win”;若塔方拥有必胜策略,则输出 “Towers win”;若游戏以平局结束,则输出 “Tie”。

3
1 1
10
10
9
11
2 2
1 1
5 4
2 1
4 2
3 3
1 2 3
1 4 9
1 4 9
1 2 3
Units win
Towers win
Tie

提示

翻译由 DeepSeek V3.2 完成