codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.