codeforces-scrape

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

2258B2.md (3103B)


      1 Source: https://codeforces.com/problemset/problem/2258/B2
      2 
      3 B2. Carrot Chopdown (Hard Version)
      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 This is the hard version of the problem. The difference between the versions is that in this version, you need to solve the problem for different values of $k$. You can hack only if you solved all versions of this problem.
     22 
     23 Alp loves carrots. Since he hasn't eaten lunch yet, he wants to buy a carrot salad to eat outside. However, he has a weird obsession: all the carrots must be the exact same length; otherwise, the salad doesn't look aesthetically pleasing to him. Since he is in the middle of the street and doesn't have a knife, he can't cut the carrots himself. You need to divide all the carrots using your machine and sell them to Alp.
     24 
     25 You are given $n$ delicious carrots with sizes $a_1, a_2, \ldots, a_n$. You are also given a cutting machine, which works as follows.
     26 
     27 * For each operation, you choose a set of carrots (you can choose chopped carrots again) and a positive integer $x$ (not necessarily the same for each operation).
     28 * After that, consider every chosen carrot, let its length be $l$. If $l \le x$, this carrot is unaffected; otherwise, it is divided into two carrots of sizes $x$ and $l-x$.
     29 
     30 We'll sell some of the final carrots to an interesting guy who wants them all to be the same length.
     31 
     32 We are asking you to determine the maximum number of carrots we can sell after using this machine exactly $k$ times. Solve the problem for each $k = 1, 2, \ldots, m$ independently.
     33 
     34 Input
     35 
     36 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.
     37 
     38 The first line of each test case contains $n$ and $m$ ($1 \le n,m \le 2 \cdot 10^5$), denoting the number of carrots and the maximum possible length of a carrot.
     39 
     40 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le m$), denoting the initial carrot sizes.
     41 
     42 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ and the sum of $m$ over all test cases does not exceed $2 \cdot 10^5$.
     43 
     44 Output
     45 
     46 For each test case, output $m$ integers — the answer for each $k=1, 2, \ldots, m$.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 6
     54 
     55 5 4
     56 
     57 1 2 3 4 4
     58 
     59 5 8
     60 
     61 1 1 8 8 8
     62 
     63 1 8
     64 
     65 6
     66 
     67 7 9
     68 
     69 1 7 5 1 7 5 3
     70 
     71 4 1
     72 
     73 1 1 1 1
     74 
     75 3 5
     76 
     77 3 1 5
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 6 14 14 14
     84 
     85 6 12 26 26 26 26 26 26
     86 
     87 2 3 6 6 6 6 6 6
     88 
     89 7 17 29 29 29 29 29 29 29
     90 
     91 4
     92 
     93 3 7 9 9 9
     94 ```
     95 
     96 Note
     97 
     98 In the first test case, the given carrots are $[1, 2, 3, 4, 4]$.
     99 
    100 For $k=1$, it is best to choose $x=2$ with the set $[2, 3, 4, 4]$. After the operation, we'll get $[1, 2, 2, 1, 2, 2, 2, 2]$. We can sell $6$ carrots of length $2$.
    101 
    102 For $k=2$, it is best to choose $x=2$ with the set $[2, 3, 4, 4]$. After the operation, we'll get $[1, 2, 2, 1, 2, 2, 2, 2]$. For the second operation, it is best to choose $x=1$ with the set of all of the carrots. Resulting in $14$ carrots, all of the same length. We can sell $14$ carrots of length $1$.