codeforces-scrape

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

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$.