turns-00030.parquet:24840
e37f52c0046e866d08c1d822degenerate_repetitionAbsentFinal dense release
USER
i want u to act as the most skilled competetive programmer, u take time to think and check if ur solution works and match up with the example tescase, u need to think thoroughly since u r in a contest.
use need to use this template, make sure u have lowercase short variable names and NO COMMENTS (in the code):
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
cin.tie(0);
ios_base::sync_with_stdio(false);
}
C. Cards Partition
time limit per test2 seconds
memory limit per test256 megabytes
DJ Genki vs Gram - Einherjar Joker
⠀
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 ai
cards which have the number i
written on them.
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 1
and n
, inclusive.
After buying the new cards, you must partition all your cards into decks, according to the following rules:
all the decks must have the same size;
there are no pairs of cards with the same value in the same deck.
Find the maximum possible size of a deck after buying cards and partitioning them optimally.
Input
Each test contains multiple test cases. The first line contains the number of test cases t
(1≤t≤104
). The description of the test cases follows.
The first line of each test case contains two integers n
, k
(1≤n≤2⋅105
, 0≤k≤1016
) — the number of distinct types of cards and the number of coins.
The second line of each test case contains n
integers a1,a2,…,an
(0≤ai≤1010
, ∑ai≥1
) — the number of cards of type i
you have at the beginning, for each 1≤i≤n
.
It is guaranteed that the sum of n
over all test cases does not exceed 2⋅105
.
Output
For each test case, output a single integer: the maximum possible size of a deck if you operate optimally.
Example
InputCopy
9
3 1
3 2 2
5 4
2 6 1 2 4
2 100
1410065408 10000000000
10 8
7 4 6 6 9 3 10 2 8 7
2 12
2 2
2 70
0 1
1 0
1
3 0
2 1 2
3 1
0 3 3
OutputCopy
2
3
1
7
2
2
1
1
2
Note
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
.
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
.ASSISTANT
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
cin.tie(0);
ios_base::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
vector<int>a(n);
int sum=0, mx=0;
for(auto &x:a){cin>>x; sum+=x; mx = max(mx, x);}
int l=1, r = sum +k, ans=1;
while(l<=r)
{
int mid = l + (r-l)/2;
int m_decks = max( (sum + mid -1)/mid, mx);
if(m_decks * mid - sum <=k)
{
ans = mid;
l = mid +1;
}
else
{
r = mid -1;
}
}
cout<<ans<<"\n";
}
}
```