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

У вас есть несколько карт. На каждой карте написано целое число от 1 до n: в частности,…

  1. User

    У вас есть несколько карт. На каждой карте написано целое число от 1 до n: в частности, для каждого i от 1 до n у вас есть ai карт, на которых написано число i

    .

    Также существует магазин, в котором продается неограниченное количество карт каждого типа. У вас есть k монет, поэтому вы можете купить в общей сложности не более k новых карт, и карты, которые вы покупаете, могут содержать любые целые числа от 1 до n

    , включительно.

    После покупки новых карт вы должны разбить все свои карты на колоды согласно следующим правилам:

    все колоды должны иметь одинаковый размер;
    нет пары карт с одинаковым числом в одной колоде. 
    

    Найдите максимально возможный размер колоды после покупки карт и их оптимального разбиения. Входные данные

    Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число t (1≤t≤104

    ) — количество наборов входных данных. Далее следует описание наборов входных данных.

    Первая строка каждого набора входных данных содержит два целых числа n , k (1≤n≤2⋅105, 0≤k≤1016

    ) — количество различных типов карт и количество монет.

    Вторая строка каждого набора входных данных содержит n целых чисел a1,a2,…,an (0≤ai≤1010, ∑ai≥1) — количество карт типа i, имеющихся у вас в начале, для каждого 1≤i≤n

    .

    Гарантируется, что сумма n по всем наборам входных данных не превосходит 2⋅105

    . Выходные данные

    Для каждого набора входных данных выведите одно целое число — максимально возможный размер колоды при оптимальных действиях. Пример Входные данные Скопировать

    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

    Выходные данные Скопировать

    2 3 1 7 2 2 1 1 2

    Примечание

    В первом наборе входных данных вы можете купить одну карту с числом 1 , и ваш набор карт станет таким: [1,1,1,1,2,2,3,3]. Вы можете разбить их на колоды [1,2],[1,2],[1,3],[1,3]. Они все имеют размер 2, и все содержат разные значения. Можно показать, что невозможно получить разбиение с колодами размером больше 2, поэтому ответ — 2

    .

    Во втором наборе входных данных вы можете купить две карты с числом 1 и одну карту с числом 3, и ваш набор карт станет таким: [1,1,1,1,2,2,2,2,2,2,3,3,4,4,5,5,5,5]. Его можно разбить на колоды [1,2,3],[1,2,4],[1,2,5],[1,2,5],[2,3,5],[2,4,5]. Можно показать, что нельзя получить разбиение с колодами размером больше 3, поэтому ответ — 3.

    реши на C++ эту олимпиадную задачу. код пиши в олимпиадном стиле, с однобуквенными переменными и без комментариев //

  2. Assistant
    #include<bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin>>t;
        while(t--){
            ll n,k;
            cin>>n>>k;
            vector<ll>a(n);
            ll sum=0, maxa=0;
            for(auto &x:a){
                cin>>x;
                sum +=x;
                if(x > maxa) maxa =x;
            }
            ll l=1, r=n, ans=1;
            while(l <=r){
                ll mid = l + (r - l)/2;
                // Compute ceil(sum / mid)
                ll t_val = (sum + mid -1)/mid;
                t_val = max(t_val, maxa);
                // Compute t_val * mid - sum
                // Check if t_val * mid - sum <=k
                if(t_val > 1e18 / mid){
                    // Overflow, set to k+1 to make it invalid
                    if(k < 1e18){
                        // Some large number
                        // t_val * mid - sum would be >k
                        // so set condition to false
                        r = mid -1;
                        continue;
                    }
                }
                ll need = t_val * mid - sum;
                if(need <=k){
                    ans = mid;
                    l = mid +1;
                }
                else{
                    r = mid -1;
                }
            }
            cout<<ans<<"\n";
        }
    }