codeforces-scrape

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

1967A.md (2477B)


      1 Source: https://codeforces.com/problemset/problem/1967/A
      2 
      3 A. Permutation Counting
      4 
      5 time limit per test
      6 
      7 2 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 You have some cards. An integer between $1$ and $n$ is written on each card: specifically, for each $i$ from $1$ to $n$, you have $a_i$ cards which have the number $i$ written on them.
     22 
     23 There is also a shop which contains unlimited cards of each type. You have $k$ coins, so you can buy $k$ new cards in total, and the cards you buy can contain any integer between $1$ and $n$.
     24 
     25 After buying the new cards, you rearrange all your cards in a line. The score of a rearrangement is the number of (contiguous) subarrays of length $n$ which are a permutation of $[1, 2, \ldots, n]$. What's the maximum score you can get?
     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 100)$. The description of the test cases follows.
     30 
     31 The first line of each test case contains two integers $n$, $k$ ($1\le n \le 2 \cdot 10^5$, $0\le k \le 10^{12}$) — the number of distinct types of cards and the number of coins.
     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^{12}$) — the number of cards of type $i$ you have at the beginning.
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case, output a single line containing an integer: the maximum score you can get.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 8
     47 
     48 1 10
     49 
     50 1
     51 
     52 2 4
     53 
     54 8 4
     55 
     56 3 4
     57 
     58 6 1 8
     59 
     60 3 9
     61 
     62 7 6 2
     63 
     64 5 3
     65 
     66 6 6 7 4 6
     67 
     68 9 7
     69 
     70 7 6 1 7 6 2 4 3 3
     71 
     72 10 10
     73 
     74 1 3 1 2 1 9 3 5 7 5
     75 
     76 9 8
     77 
     78 5 8 7 5 1 3 2 9 8
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 11
     85 
     86 15
     87 
     88 15
     89 
     90 22
     91 
     92 28
     93 
     94 32
     95 
     96 28
     97 
     98 36
     99 ```
    100 
    101 Note
    102 
    103 In the first test case, the final (and only) array we can get is $[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]$ (including $11$ single $1$s), which contains $11$ subarrays consisting of a permutation of $[1]$.
    104 
    105 In the second test case, we can buy $0$ cards of type $1$ and $4$ cards of type $2$, and then we rearrange the cards as following: $[1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]$. There are $8$ subarrays equal to $[1, 2]$ and $7$ subarrays equal to $[2, 1]$, which make a total of $15$ subarrays which are a permutation of $[1, 2]$. It can also be proved that this is the maximum score we can get.
    106 
    107 In the third test case, one of the possible optimal rearrangements is $[3, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 3]$.