Skip to content
TheChatArchiveThe Chat Archive
o1-mini-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

optimum cpp code for : Cards Partition time limit per test2 seconds memory limit per…

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

  2. 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:

    1. Card Types and Counts: We have n types of cards, with a_i cards initially of each type. We can purchase up to k additional cards.
    2. 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).

    Objective:

    To maximize the deck size s.

    Approach:

    1. Binary Search Setup: We perform a binary search for s in the range [1, n], where n is the number of card types.
    2. 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.
      • 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 to k additional cards.
      • Check Feasibility:
        • If m_required is less than or equal to m_max, then it's feasible to form decks of size s. Otherwise, it's not feasible.
    3. Update Search Space:
      • If feasible, update the answer and search for a larger s.
      • If not feasible, search for a smaller s.
    4. Final Output: The maximum feasible s found 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 = 2 is 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";
        }
    }