← 返回题目列表

Codeforces · 1530/C

C. 追求

中文机器翻译题面 查看原题

您和您的朋友 Ilya 正在参加由多个阶段组成的个人编程竞赛。参赛者在每个阶段可以获得 $$$0$$$ 到 $$$100$$$ 积分(含),与其他参赛者无关。

Points received by contestants in different stages are used for forming overall contest results.假设比赛已完成 $$$k$$$ 个阶段。对于每位参赛者,选择得分最高的 $$$k - \lfloor \frac{k}{4} \rfloor$$$ 阶段,并将这些分数相加。这个总和就是参赛者的总成绩。 (这里 $$$\lfloor t \rfloor$$$ 表示向下舍入 $$$t$$$。)

例如,假设已完成 $$$9$$$ 个阶段,并且您的分数为 $$$50, 30, 50, 50, 100, 10, 30, 100, 50$$$。首先,选择得分最高的 $$$7$$$ 阶段 - 例如,可以选择除 $$$2$$$-nd 和 $$$6$$$-th 之外的所有阶段。那么您的总结果等于 $$$50 + 50 + 50 + 100 + 30 + 100 + 50 = 430$$$。

到目前为止,$$$n$$$阶段已经完成,你知道你和伊利亚在这些阶段获得的分数。不过,目前还不清楚还会举办多少个阶段。您想知道最少的附加阶段数是多少,之后您的结果可能会大于或等于 Ilya 的结果,至少在理论上是这样。找到这个号码!

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of completed stages.

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 100$$$) - 您完成阶段的分数。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 100$$$) — Ilya 已完成阶段的分数。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印一个整数 - 您的结果能够大于或等于 Ilya 的结果所需的最小附加阶段数。

如果您的结果已经不小于 Ilya 的结果,请打印 $$$0$$$。

示例

输入 #1

5
1
100
0
1
0
100
4
20 30 40 50
100 100 100 100
4
10 20 30 40
100 100 100 100
7
7 59 62 52 27 31 55
33 35 50 98 83 80 64

输出 #1

0
1
3
4
2

注意

在第一个测试用例中,您在第一阶段获得了 $$$100$$$ 分,而 Ilya 则获得了 $$$0$$$ 分。因此,您的总成绩 ($$$100$$$) 已经不低于 Ilya 的成绩 ($$$0$$$)。

In the second test case, you have scored $$$0$$$ points for the first stage, while Ilya has scored $$$100$$$. A single stage with an opposite result is enough for both your and Ilya's overall scores to become equal to $$$100$$$.

在第三个测试用例中,您的总结果是 $$$30 + 40 + 50 = 120$$$,而 Ilya 的结果是 $$$100 + 100 + 100 = 300$$$。经过三个额外阶段后,您的结果可能会变为 $$$420$$$,而 Ilya 的结果可能会变为 $$$400$$$。

在第四个测试用例中,四个附加阶段后的总体结果可能会等于 $$$470$$$,而 Ilya 的结果可能会等于 $$$400$$$。三个阶段还不够。