2018A.md (2774B)
1 Source: https://codeforces.com/problemset/problem/2018/A 2 3 A. Cards Partition 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 [DJ Genki vs Gram - Einherjar Joker](https://soundcloud.com/leon-hwang-368077289/einherjar-joker-dj-genki-vs-gram) 22 23 ⠀ 24 25 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. 26 27 There is also a shop which contains unlimited cards of each type. You have $k$ coins, so you can buy at most $k$ new cards in total, and the cards you buy can contain any integer between $\mathbf{1}$ and $\mathbf{n}$, inclusive. 28 29 After buying the new cards, you must partition all your cards into decks, according to the following rules: 30 31 * all the decks must have the same size; 32 * there are no pairs of cards with the same value in the same deck. 33 34 Find the maximum possible size of a deck after buying cards and partitioning them optimally. 35 36 Input 37 38 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. 39 40 The first line of each test case contains two integers $n$, $k$ ($1 \leq n \leq 2 \cdot 10^5$, $0 \leq k \leq 10^{16}$) — the number of distinct types of cards and the number of coins. 41 42 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^{10}$, $\sum a_i \geq 1$) — the number of cards of type $i$ you have at the beginning, for each $1 \leq i \leq n$. 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 maximum possible size of a deck if you operate optimally. 49 50 Example 51 52 Input 53 54 ``` 55 9 56 57 3 1 58 59 3 2 2 60 61 5 4 62 63 2 6 1 2 4 64 65 2 100 66 67 1410065408 10000000000 68 69 10 8 70 71 7 4 6 6 9 3 10 2 8 7 72 73 2 12 74 75 2 2 76 77 2 70 78 79 0 1 80 81 1 0 82 83 1 84 85 3 0 86 87 2 1 2 88 89 3 1 90 91 0 3 3 92 ``` 93 94 Output 95 96 ``` 97 2 98 3 99 1 100 7 101 2 102 2 103 1 104 1 105 2 106 ``` 107 108 Note 109 110 In the first test case, you can buy one card with the number $1$, and your cards become $[1, 1, 1, 1, 2, 2, 3, 3]$. You can partition them into the decks $[1, 2], [1, 2], [1, 3], [1, 3]$: they all have size $2$, and they all contain distinct values. You can show that you cannot get a partition with decks of size greater than $2$, so the answer is $2$. 111 112 In the second test case, you can buy two cards with the number $1$ and one card with the number $3$, and your cards become $[1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5]$, which can be partitioned into $[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 2, 5], [2, 3, 5], [2, 4, 5]$. You can show that you cannot get a partition with decks of size greater than $3$, so the answer is $3$.