[Solution] Pebbles and Beads solution codeforces

Pebbles and Beads solution codeforces – There are two currencies: pebbles and beads. Initially you have 𝑎a pebbles, 𝑏b beads.

Table of Contents

[Solution] Pebbles and Beads solution codeforces

There are 𝑛n days, each day you can exchange one currency for another at some exchange rate.

On day 𝑖i, you can exchange 𝑝𝑖𝑥𝑝𝑖−pi≤x≤pi pebbles for 𝑞𝑖𝑦𝑞𝑖−qi≤y≤qi beads or vice versa. It’s allowed not to perform an exchange at all. Meanwhile, if you perform an exchange, the proportion 𝑥𝑞𝑖=𝑦𝑝𝑖x⋅qi=−y⋅pi 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.

[Solution] Pebbles and Beads solution codeforces

The first line of the input contains a single integer 𝑡t (1𝑡1031≤t≤103) — 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𝑛3000001≤n≤3000000𝑎,𝑏1090≤a,b≤109) — the number of days and the initial number of pebbles and beads respectively.

The second line of each test case contains 𝑛n integers: 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn (1𝑝𝑖1091≤pi≤109).

The third line of each test case contains 𝑛n integers: 𝑞1,𝑞2,,𝑞𝑛q1,q2,…,qn (1𝑞𝑖1091≤qi≤109).

It is guaranteed that the sum of 𝑛n over all test cases doesn’t exceed 300000300000.

[Solution] Pebbles and Beads solution codeforces

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 10610−6.

Formally, let your answer be 𝑎a, and the jury’s answer be 𝑏b. Your answer is accepted if and only if |𝑎𝑏|max(1,|𝑏|)106|a−b|max(1,|b|)≤10−6.

Example
input

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

[Solution] Pebbles and Beads solution codeforces

Copy
6
8
4
6
9.000000
10.33
Note

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.

[Solution] Pebbles and Beads solution codeforces

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 11 pebble for 22 beads, which is a correct exchange, since 14=221⋅4=2⋅2, and then to exchange 22 beads for 33 pebbles.

 

For Solution

“Click Here”

Leave a Comment