#BZOJ3983. Takeover Wars

Takeover Wars

题目描述

你正在学习一个两个公司间的商业战争,它们分别是X和Y(译者注:原文名称太复杂,这里简记).每一个公司包含一系列的子公司。这次战争可以看做是市场战争,X有n个子公司而Y有m个子公司(1<=n,m<=10^5),你知道每个子公司的市场价值。
每个子公司可以决定一个子公司来进行一次交易,交易既可以是友好的,也可以是敌对的。一个友好的交易意味着同属于一个公司子公司和子公司之间的合并。一次合并产生的新的子公司的市场价值是参与交易双方的价值之和。一次友好交易中,子公司的大小没有限制。
一个敌对的交易意味着一个子公司A(既可以是X也可以是Y)希望和子公司B交易。为了让交易顺利进行,A的市场价值必须大于B的。这样做之后,B从市场上消失,A的市场价值不变。为了简化问题,我们可以认为,所有的操作序列不会出现相同价值的子公司间的交易。
公司轮流行动,X先动。一个公司什么都不做当且仅当它什么都不能做。如果一个公司的是子公司全没了,那么它就输掉了这场商业竞争。
你的目标算出哪个公司一定能赢得胜利。在样例一中,X公司可以用7-价值公司干掉Y的一个子公司。然后Y只能干掉X的一个1-价值公司,然后Y的最后一个公司就被干掉了。在样例二中,X公司一开始只能合并它的两个公司变为6-价值公司,Y此时应该用友好操作合并2个5-价值公司为10-价值公司。X就只能继续合并,但无论它怎么合并,都会被Y的10-公司吃掉一个,然后X只能pass,Y就再吃一个,就取胜了。

输入格式

每个测试数据包含三行。第一行两个数n,m表示X和Y的子公司数。第二行n个数描述X的子公司价值(用空格隔开),第三行m个数描述Y的子公司价值(用空格隔开)(价值<=10^12)。

输出格式

对于每组数据,先输出测试数据组号,若X胜利,输出"Takeover Incorporated",否则输出"Buyout Limited"。(译者注:其实这就是那个很复杂的名字。)

3 2
7 1 1
5 5
4 2
3 3 3 3
5 5
Case 1: Takeover Incorporated
Case 2: Buyout Limited