2194B.md (2647B)
1 Source: https://codeforces.com/problemset/problem/2194/B 2 3 B. Offshores 4 5 time limit per test 6 7 1.5 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Mark loves money very much, and he keeps most of it in the bank. He stores his money in $n$ different banks. In the $i$-th bank, he has $a_i$ rubles. 22 23 One day, Mark decided to gather all his money in one bank, so he will be transferring money from one bank account to another. All interbank transfers are arranged the same way: he can transfer only $x$ rubles in one transfer, and considering all fees, $y$ rubles will be credited to the other account (since banks want to make a profit, it holds that $y \leq x$). 24 25 It is possible that Mark will not be able to transfer all his money to one bank, but he wants to find the maximum number of rubles that can end up in any bank. 26 27 Input 28 29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 30 31 The first line of each test case contains three integers $n$, $x$, and $y$ ($2 \le n \le 2 \cdot 10^5$, $1 \le y \le x \le 10^9$) — the number of banks, the transfer amount, and the credited amount. 32 33 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the initial amount of rubles in each bank. 34 35 It is guaranteed that the sum of the values of $n$ across all test cases does not exceed $2 \cdot 10^5$. 36 37 Output 38 39 For each test case, output a single number — the maximum number of rubles that can be obtained in any bank. 40 41 Example 42 43 Input 44 45 ``` 46 6 47 48 4 5 4 49 50 10 9 8 7 51 52 5 13 11 53 54 47 52 64 13 91 55 56 2 1 1 57 58 1000 1000 59 60 3 15 14 61 62 34 43 52 63 64 6 7 6 65 66 15 17 14 15 12 16 67 68 2 15 10 69 70 45 44 71 ``` 72 73 Output 74 75 ``` 76 25 77 78 229 79 80 2000 81 82 113 83 84 72 85 86 74 87 ``` 88 89 Note 90 91 In the first test case, the optimal sequence of transfers may look as follows: $$ 1\to4,\; 1\to4,\; 4\to3,\; 4\to3,\; 4\to3,\; 3\to2,\; 3\to2,\; 3\to2,\; 3\to2. $$ Let's show the changes in sums after each step: $$ (10,9,8,7) $$ $$ \xrightarrow{1\to4} (5,9,8,11) \xrightarrow{1\to4} (0,9,8,15) $$ $$ \xrightarrow{4\to3} (0,9,12,10) \xrightarrow{4\to3} (0,9,16,5) \xrightarrow{4\to3} (0,9,20,0) $$ $$ \xrightarrow{3\to2} (0,13,15,0) \xrightarrow{3\to2} (0,17,10,0) \xrightarrow{3\to2} (0,21,5,0) \xrightarrow{3\to2} (0,25,0,0). $$ 92 93 As a result, in one bank (specifically the second one), it is possible to obtain $25$ rubles, and this value is the answer for this test case. 94 95 In the third test case, it is possible to transfer one ruble from the first bank to the second bank $1000$ times and obtain $2000$ rubles in the second bank.