← 返回题目列表

Codeforces · 1735/F

F. 鹅卵石和珠子

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

有两种货币:卵石和珠子。最初你有 $$$a$$$ 鹅卵石,$$$b$$$ 珠子。

有 $$$n$$$ 天,每天您都可以按某种汇率将一种货币兑换成另一种货币。

在 $$$i$$$ 天,您可以将 $$$-p_i \leq x \leq p_i$$$ 鹅卵石交换为 $$$-q_i \leq y \leq q_i$$$ 珠子,反之亦然。完全不进行交换是允许的。同时,如果进行交换,则必须满足$$$x \cdot q_i = -y \cdot p_i$$$ 的比例。允许小数交换。

您一天内最多只能进行一次此类交换。您拥有的卵石和珠子的数量必须始终保持非负数。

请独立解决以下 $$$n$$$ 问题:对于每一天 $$$i$$$,输出如果您以最佳方式进行交换,则在一天结束时 $$$i$$$ 可以拥有的最大卵石数量。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$a$$$ 和 $$$b$$$ ($$$1 \le n \le 300\,000$$$, $$$0 \le a, b \le 10^9$$$) — 分别是天数和卵石和珠子的初始数量。

每个测试用例的第二行包含 $$$n$$$ 整数:$$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le 10^9$$$)。

每个测试用例的第三行包含 $$$n$$$ 整数:$$$q_1, q_2, \ldots, q_n$$$ ($$$1 \le q_i \le 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$300\,000$$$。

输出

输出 $$$n$$$ 数字 — 每天结束时卵石的最大数量。

如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。

正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{\left|a - b\right|}{\max(1, \left|b\right|)} \le 10^{-6}$$$ 时,您的答案才会被接受。

示例

输入 #1

3
2 6 0
2 3
4 2
3 0 6
4 2 10
2 3 10
1 10 10
33
1000

输出 #1

6
8
4
6
9.000000
10.33

注意

在下图中,您可以看到前两个测试用例的解决方案。每行都有每天的最佳行动顺序。

在第一个测试用例中,第一天的最佳策略是根本不执行任何操作,因为我们只能减少卵石的数量。第二天的最佳策略是首先用 $$$1$$$ 卵石交换 $$$2$$$ 珠子,这是正确的交换,因为 $$$1 \cdot 4 = 2 \cdot 2$$$,然后用 $$$2$$$ 珠子交换 $$$3$$$ 卵石。