codeforces-scrape

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

2024B.md (4051B)


      1 Source: https://codeforces.com/problemset/problem/2024/B
      2 
      3 B. Buying Lemonade
      4 
      5 time limit per test
      6 
      7 1 second
      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 There is a vending machine that sells lemonade. The machine has a total of $n$ slots. You know that initially, the $i$-th slot contains $a_i$ cans of lemonade. There are also $n$ buttons on the machine, each button corresponds to a slot, with exactly one button corresponding to each slot. Unfortunately, the labels on the buttons have worn off, so you do not know which button corresponds to which slot.
     22 
     23 When you press the button corresponding to the $i$-th slot, one of two events occurs:
     24 
     25 * If there is a can of lemonade in the $i$-th slot, it will drop out and you will take it. At this point, the number of cans in the $i$-th slot decreases by $1$.
     26 * If there are no cans of lemonade left in the $i$-th slot, nothing will drop out.
     27 
     28 After pressing, the can drops out so quickly that it is impossible to track from which slot it fell. The contents of the slots are hidden from your view, so you cannot see how many cans are left in each slot. The only thing you know is the initial number of cans in the slots: $a_1, a_2, \ldots, a_n$.
     29 
     30 Determine the minimum number of button presses needed to guarantee that you receive at least $k$ cans of lemonade.
     31 
     32 Note that you can adapt your strategy during the button presses based on whether you received a can or not. It is guaranteed that there are at least $k$ cans of lemonade in total in the machine. In other words, $k \leq a_1 + a_2 + \ldots + a_n$.
     33 
     34 Input
     35 
     36 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
     37 
     38 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \leq k \leq 10^9$) — the number of slots in the machine and the required number of cans of lemonade.
     39 
     40 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 number of cans in the slots.
     41 
     42 It is guaranteed that $k \leq a_1 + a_2 + \ldots + a_n$, meaning there are at least $k$ cans of lemonade in the machine.
     43 
     44 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     45 
     46 Output
     47 
     48 For each test case, output a single integer — the minimum number of button presses needed to guarantee that you receive at least $k$ cans of lemonade.
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 5
     56 
     57 2 1
     58 
     59 1 1
     60 
     61 2 2
     62 
     63 1 2
     64 
     65 3 4
     66 
     67 2 1 3
     68 
     69 10 50
     70 
     71 1 1 3 8 8 9 12 13 27 27
     72 
     73 2 1000000000
     74 
     75 1000000000 500000000
     76 ```
     77 
     78 Output
     79 
     80 ```
     81 1
     82 2
     83 5
     84 53
     85 1000000000
     86 ```
     87 
     88 Note
     89 
     90 In the first test case, we can simply press the first button and receive one can of lemonade.
     91 
     92 In the second test case, we can press each button once and guarantee that we receive $2$ cans of lemonade. Note that if we simply press one button twice, we might not be lucky, and that button could correspond to the first slot, in which case we would only receive $1$ can of lemonade for two presses.
     93 
     94 In the third test case, one of the optimal strategies is as follows:
     95 
     96 Press the first button twice. After the first press, a can of lemonade will definitely drop out. Then there are two options:
     97 
     98 * If no can of lemonade drops after the second press, we know that this button must correspond to the second slot, since $a_2 = 1$ and $a_1, a_3 \gt 1$. Then we can press the second button twice and the third button once. Since $a_1, a_3 \geq 2$, we will definitely receive three cans of lemonade for these three presses. Thus, after $5$ presses, we will have $4$ cans of lemonade.
     99 * If a can of lemonade drops after the second press, we can make one press on the second button and one press on the third button. After each of these presses, we will definitely receive a can of lemonade. Thus, after $4$ presses, we will have $4$ cans of lemonade.
    100 
    101 It can be shown that it is impossible to guarantee receiving $4$ cans of lemonade with only $4$ presses, so the answer is $5$.