i want u to act as the most skilled competetive programmer, u take time to think and…
- 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
#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; int k; cin >> n >> k; vector<int> a(n); int sum=0, maxa=0; for(auto &x: a){ cin >> x; sum +=x; if(x > maxa) maxa =x; } if(maxa ==0){ cout << min(n, (sum +k)) << "\n"; continue; } int r = min(n, (sum +k)/maxa); if(r ==0){ r=1; } int l=1; int ans=1; while(l <=r){ int mid = l + (r -l)/2; int D1 = (sum + mid -1)/mid; int D = max(D1, maxa); int floor_val = (sum +k)/mid; if(D <= floor_val){ ans = mid; l = mid +1; } else{ r = mid -1; } } cout << ans << "\n"; } }
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.