完整题面和翻译
查看原帖
完整题面和翻译
119491
5ab_juruo楼主2022/8/3 16:39

原题面:

You are studying a takeover war between two large corporations, Takeover Incorporated and Buyout Limited. Each of these corporations controls a number of subsidiaries. The aim in this war is simply to drive the competition out of the market. There are N subsidiaries of Takeover Incorporated and M subsidiaries of Buyout Limited, and you know the market value of each subsidiary.

Each company can designate one of its subsidiaries to perform a takeover. The takeover can either be friendly or hostile. A friendly takeover means a subsidiary of a corporation merges with a different subsidiary of the same corporation. The market value of the merged subsidiary is the sum of the market values of the constituent subsidiaries. There is no constraint on the relative sizes of the subsidiaries participating in a friendly takeover.

A hostile takeover means a subsidiary A of a corporation attempts to take over a subsidiary B of the other corporation. For this to succeed, the market value of A has to be greater than the market value of B. After this move, B disappears from the market. The market value of A does not change (the gain of incorporating B’s assets is offset by the monetary cost of the takeover). For simplicity we assume that no sequence of moves leads to two subsidiaries of different corporations having the same market value. The companies take turns making moves in this takeover war, with Takeover Incorporated going first. A company will do nothing on its turn only if it cannot make a takeover. A company loses the takeover war if all its subsidiaries are taken over.

Your aim is to learn which company can guarantee a victory from this war. In the first case of the sample data, Takeover Incorporated can simply take over one of the companies of Buyout Limited in its first move with the 7-value subsidiary. Then it will lose one of its small (1-value) subsidiaries to a hostile takeover, and then it will take over the second subsidiary of Buyout Limited. In the second case, Takeover has to make a friendly takeover in its first move. Buyout Limited will join its two subsidiaries into a single company with market value 10. Takeover will have to make a friendly takeover again (as again it will not have a large enough subsidiary to take over Buyout’s giant). Now Takeover will have two subsidiaries, valued either 9 and 3 or 6 and 6. In either case, Buyout takes over one of these subsidiaries, Takeover has to pass, and Buyout takes over the other one.

Input
Each test case is described by three lines of input. The first line contains two numbers 1 ≤ N ≤ 10 5 and 1 ≤ M ≤ 10 5 denoting respectively the number of subsidiaries of Takeover Incorporated and Buyout Limited. The next line lists the N sizes a i of the subsidiaries of Takeover Incorporated (1 ≤ a i ≤ 10 12 ), and the third line lists the M sizes b j of the subsidiaries of Buyout Limited (1 ≤ b j ≤ 10 12 ).

Output
For each test case, display the case number and either the phrase Takeover Incorporated or the phrase Buyout Limited depending on who wins the takeover war if both corporations act optimally.

翻译:

Takeover Incorporated 和 Buyout Limited 两家公司在竞争。Takeover Incorporated 有 nn 家子公司而 Buyout Limited 有 mm 家子公司。每家子公司有一个权值。两家公司轮流操作,每次操作可以执行一下两种收购之一:

  1. 友好的收购,即将自家两家子公司合并,合并后的子公司权值为原两家子公司权值之和。
  2. 有敌意的收购,即当自家的子公司权值大于对手的一家子公司的权值时,用自家的子公司去吞并对手的子公司,对手的子公司消失,而自家不变。

Takeover Incorporated 先操作,如果两家公司都按照最优方案操作,问谁能获胜。

输入格式

每个测试点有多组数据。需要读入到文件末尾。

对于每组数据,第一行输入 n,mn,m。接下来一行 nn 个数 aia_i 代表 Takeover Incorporated 每家子公司的权值。接下来一行 mm 个数 bib_i 代表 Buyout Limited 每家子公司的权值。

输出格式

对于第 ii 组数据,先输出 Case i: (冒号后面有空格),然后输出 Takeover IncorporatedBuyout Limited,代表最终获胜的公司。

Takeover Incorporated 和 Buyout Limited 两家公司在竞争。Takeover Incorporated 有 $n$ 家子公司而 Buyout Limited 有 $m$ 家子公司。每家子公司有一个权值。两家公司轮流操作,每次操作可以执行一下两种收购之一:

1. 友好的收购,即将自家两家子公司合并,合并后的子公司权值为原两家子公司权值之和。
2. 有敌意的收购,即当自家的子公司权值大于对手的一家子公司的权值时,用自家的子公司去吞并对手的子公司,对手的子公司消失,而自家不变。

Takeover Incorporated 先操作,如果两家公司都按照最优方案操作,问谁能获胜。

### 输入格式

**每个测试点有多组数据**。需要读入到文件末尾。

对于每组数据,第一行输入 $n,m$。接下来一行 $n$ 个数 $a_i$ 代表 Takeover Incorporated 每家子公司的权值。接下来一行 $m$ 个数 $b_i$ 代表 Buyout Limited 每家子公司的权值。

### 输出格式

对于第 $i$ 组数据,先输出 `Case i: `(冒号后面有空格),然后输出 `Takeover Incorporated` 或 `Buyout Limited`,代表最终获胜的公司。
2022/8/3 16:39
加载中...