QOJ.ac

QOJ

実行時間制限: 1 s メモリ制限: 512 MB 満点: 100

#10450. 收购战

統計

你正在研究两家大公司 Takeover Incorporated 和 Buyout Limited 之间的收购战。这两家公司各自控制着若干子公司。这场战争的目的很简单,就是将竞争对手逐出市场。Takeover Incorporated 有 $N$ 家子公司,Buyout Limited 有 $M$ 家子公司,并且你知道每家子公司的市场价值。

每家公司都可以指定其旗下的一家子公司进行收购。收购可以是友好收购或敌意收购。友好收购意味着一家公司的子公司与同一公司的另一家子公司合并。合并后的子公司的市场价值为组成该子公司的各子公司市场价值之和。参与友好收购的子公司的大小没有限制。

敌意收购意味着一家公司的子公司 $A$ 试图收购另一家公司的子公司 $B$。要使收购成功,子公司 $A$ 的市场价值必须大于子公司 $B$ 的市场价值。在此操作后,$B$ 从市场上消失。$A$ 的市场价值保持不变(合并 $B$ 的资产所带来的收益被收购的货币成本所抵消)。为简化起见,我们假设没有任何操作序列会导致两家不同公司的子公司具有相同的市场价值。

在这场收购战中,两家公司轮流进行操作,由 Takeover Incorporated 先手。只有在无法进行任何收购时,公司才会在其回合中什么都不做。如果一家公司的所有子公司都被收购,则该公司输掉这场收购战。

你的目标是了解哪家公司能保证在这场战争中获胜。在样例数据的第一种情况中,Takeover Incorporated 可以直接在第一步操作中用价值为 7 的子公司收购 Buyout Limited 的一家公司。然后它会因为敌意收购失去一家小型(价值为 1)的子公司,接着它会收购 Buyout Limited 的第二家子公司。在第二种情况中,Takeover 在第一步必须进行友好收购。Buyout Limited 会将其两家子公司合并为一家市场价值为 10 的公司。Takeover 将不得不再次进行友好收购(因为它仍然没有足够大的子公司来收购 Buyout 的巨头)。现在 Takeover 将拥有两家子公司,价值分别为 9 和 3,或者 6 和 6。无论哪种情况,Buyout 都会收购其中一家子公司,Takeover 必须弃权,然后 Buyout 会收购另一家。

输入格式

每个测试用例由三行输入描述。第一行包含两个数字 $1 \le N \le 10^5$ 和 $1 \le M \le 10^5$,分别表示 Takeover Incorporated 和 Buyout Limited 的子公司数量。下一行列出了 Takeover Incorporated 的 $N$ 个子公司的大小 $a_i$ ($1 \le a_i \le 10^{12}$),第三行列出了 Buyout Limited 的 $M$ 个子公司的大小 $b_j$ ($1 \le b_j \le 10^{12}$)。

输出格式

对于每个测试用例,显示用例编号,并根据两家公司在最优策略下的表现,输出 Takeover IncorporatedBuyout Limited,表示谁赢得了这场收购战。

样例

输入 1

3 2
7 1 1
5 5
4 2
3 3 3 3
5 5

输出 1

Case 1: Takeover Incorporated
Case 2: Buyout Limited

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.