optimum cpp code for : Cards Partition time limit per test2 seconds memory limit per…
- User
optimum cpp code for : 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
To solve the problem of determining the maximum possible size of a deck of cards, where the constraints involve limiting the number of identical cards per deck and allowing the purchase of additional cards, we can follow a binary search approach. Here's a detailed explanation of the method:
Problem Breakdown:
- Card Types and Counts: We have
ntypes of cards, witha_icards initially of each type. We can purchase up tokadditional cards. - Deck Constraints: We need to partition all cards into decks where:
- Each deck has the same size
s. - Each deck must have unique card types (no duplicates within a deck).
- Each deck has the same size
Objective:
To maximize the deck size
s.Approach:
- Binary Search Setup: We perform a binary search for
sin the range[1, n], wherenis the number of card types. - Feasibility Check for Each
s:- Determine Minimum Decks (
m_required):- This is the maximum of two values:
ceil(total_cards / s): This ensures we have enough decks to hold all cards.max(a_i): This ensures that no single card type exceeds the number of decks.
- This is the maximum of two values:
- Determine Maximum Allowed Decks (
m_max):- This is calculated as
floor((total_cards + k) / s), which accounts for the maximum number of decks we can have after purchasing up tokadditional cards.
- This is calculated as
- Check Feasibility:
- If
m_requiredis less than or equal tom_max, then it's feasible to form decks of sizes. Otherwise, it's not feasible.
- If
- Determine Minimum Decks (
- Update Search Space:
- If feasible, update the answer and search for a larger
s. - If not feasible, search for a smaller
s.
- If feasible, update the answer and search for a larger
- Final Output: The maximum feasible
sfound through this binary search is the desired answer.
Example Walkthrough:
- For the first test case:
n = 3,k = 1, cards =[3, 2, 2].- Total cards = 7, max card type = 3.
- Binary search will determine that
s = 2is feasible, which matches the sample output.
Implementation:
Here's the C++ implementation based on the above approach:
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while(t--){ ll n, k; cin >> n >> k; vector<ll> a(n); ll sum_ai =0; ll max_ai =0; for(int i=0;i<n;i++){ cin >> a[i]; sum_ai += a[i]; if(a[i] > max_ai) max_ai = a[i]; } ll left =1, right =n; ll answer =1; while(left <=right){ ll mid = left + (right -left)/2; // m_lower = ceil(sum_ai / mid ) ll m_lower = (sum_ai + mid -1)/mid; ll m_required = max(m_lower, max_ai); // m_max = floor( (sum_ai +k ) / mid ) ll m_max = (sum_ai + k ) / mid; if(m_required <= m_max){ answer = mid; left = mid +1; } else{ right = mid -1; } } cout << answer << "\n"; } } - Card Types and Counts: We have