F - Quests.cpp

#include <bits/stdc++.h>

using namespace std;

const int MX = 2e5 + 5;
const int MX2 = 2e5;

int t, n;

long long int arr[MX], sum[MX], c, d;


bool test(int k){
    long long int days = d;
    long long int coins = sum[k] * (days / k);
    days %= k;
    coins += sum[days];
    return coins >= c;
}

int main(){
    cin.tie(nullptr), ios::sync_with_stdio(false);
    cin >> t;
    while(t--){
        cin >> n >> c >> d;
        for(int i = 1; i <= n; i++) cin >> arr[i];
        for(int i = n + 1; i <= d; i++) arr[i] = 0;
        sort(arr + 1, arr + n + 1, greater <long long int> ());
        for(int i = 1; i <= d; i++) sum[i] = sum[i - 1] + arr[i];

        if(!test(1)){
            cout << "Impossible\n";
            continue;
        }

        if(sum[d] >= c){
            cout << "Infinity\n";
            continue;
        }

        int lo = 1, hi = d;
        while(lo < hi){
            int mid = (lo + hi + 1) >> 1;
            if(test(mid)) lo = mid;
            else hi = mid - 1;
        }

        cout << (lo - 1) << "\n";
    }
}