309787: CF1735F. Pebbles and Beads
Memory Limit：256 MB
Time Limit：4 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Pebbles and Beads
题目描述
There are two currencies: pebbles and beads. Initially you have $ a $ pebbles, $ b $ beads. There are $ n $ days, each day you can exchange one currency for another at some exchange rate. On day $ i $ , you can exchange $ -p_i \leq x \leq p_i $ pebbles for $ -q_i \leq y \leq q_i $ beads or vice versa. It's allowed not to perform an exchange at all. Meanwhile, if you perform an exchange, the proportion $ x \cdot q_i = -y \cdot p_i $ must be fulfilled. Fractional exchanges are allowed. You can perform no more than one such exchange in one day. The numbers of pebbles and beads you have must always remain non-negative. Please solve the following $ n $ problems independently: for each day $ i $ , output the maximum number of pebbles that you can have at the end of day $ i $ if you perform exchanges optimally.输入输出格式
输入格式
The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 10^3 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains three integers $ n $ , $ a $ and $ b $ ( $ 1 \le n \le 300\,000 $ , $ 0 \le a, b \le 10^9 $ ) — the number of days and the initial number of pebbles and beads respectively. The second line of each test case contains $ n $ integers: $ p_1, p_2, \ldots, p_n $ ( $ 1 \le p_i \le 10^9 $ ). The third line of each test case contains $ n $ integers: $ q_1, q_2, \ldots, q_n $ ( $ 1 \le q_i \le 10^9 $ ). It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 300\,000 $ .
输出格式
Output $ n $ numbers — the maximum number of pebbles at the end of each day. Your answer is considered correct if its absolute or relative error does not exceed $ 10^{-6} $ . Formally, let your answer be $ a $ , and the jury's answer be $ b $ . Your answer is accepted if and only if $ \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说明
In the image below you can see the solutions for the first two test cases. In each line there is an optimal sequence of actions for each day. In the first test case, the optimal strategy for the first day is to do no action at all, as we can only decrease the number of pebbles. The optimal strategy for the second day is at first to exchange $ 1 $ pebble for $ 2 $ beads, which is a correct exchange, since $ 1 \cdot 4 = 2 \cdot 2 $ , and then to exchange $ 2 $ beads for $ 3 $ pebbles. Input
暂时还没有翻译
Output
**题目描述**
有两种货币：鹅卵石和珠子。最初你有 $ 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{|a - b|}{\max(1, |b|)} \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
```
**输出样例 #1**
```
6
8
4
6
9.000000
10.33
```
**说明**
在下图中，你可以看到前两个测试用例的解决方案。每行显示了每天的最优行动序列。
在第一个测试用例中，第一天最优的策略是什么都不做，因为我们只能减少鹅卵石的数量。第二天的最优策略是首先用 1 块鹅卵石兑换 2 颗珠子，这是一个正确的兑换，因为 $ 1 \cdot 4 = 2 \cdot 2 $，然后用 2 颗珠子兑换 3 块鹅卵石。
**题目描述** 有两种货币：鹅卵石和珠子。最初你有 $ 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{|a - b|}{\max(1, |b|)} \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 ``` **输出样例 #1** ``` 6 8 4 6 9.000000 10.33 ``` **说明** 在下图中，你可以看到前两个测试用例的解决方案。每行显示了每天的最优行动序列。 在第一个测试用例中，第一天最优的策略是什么都不做，因为我们只能减少鹅卵石的数量。第二天的最优策略是首先用 1 块鹅卵石兑换 2 颗珠子，这是一个正确的兑换，因为 $ 1 \cdot 4 = 2 \cdot 2 $，然后用 2 颗珠子兑换 3 块鹅卵石。 
有两种货币：鹅卵石和珠子。最初你有 $ 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{|a - b|}{\max(1, |b|)} \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
```
**输出样例 #1**
```
6
8
4
6
9.000000
10.33
```
**说明**
在下图中，你可以看到前两个测试用例的解决方案。每行显示了每天的最优行动序列。
在第一个测试用例中，第一天最优的策略是什么都不做，因为我们只能减少鹅卵石的数量。第二天的最优策略是首先用 1 块鹅卵石兑换 2 颗珠子，这是一个正确的兑换，因为 $ 1 \cdot 4 = 2 \cdot 2 $，然后用 2 颗珠子兑换 3 块鹅卵石。
**题目描述** 有两种货币：鹅卵石和珠子。最初你有 $ 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{|a - b|}{\max(1, |b|)} \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 ``` **输出样例 #1** ``` 6 8 4 6 9.000000 10.33 ``` **说明** 在下图中，你可以看到前两个测试用例的解决方案。每行显示了每天的最优行动序列。 在第一个测试用例中，第一天最优的策略是什么都不做，因为我们只能减少鹅卵石的数量。第二天的最优策略是首先用 1 块鹅卵石兑换 2 颗珠子，这是一个正确的兑换，因为 $ 1 \cdot 4 = 2 \cdot 2 $，然后用 2 颗珠子兑换 3 块鹅卵石。 