Quests (Codeforces 1760F)
Tags: Greedy, sortings

There are $$$n$$$ quests. If you complete the $$$i$$$-th quest, you will gain $$$a_i$$$ coins. You can only complete at most one quest per day. However, once you complete a quest, you cannot do the same quest again for $$$k$$$ days. (For example, if $$$k=2$$$ and you do quest $$$1$$$ on day $$$1$$$, then you cannot do it on day $$$2$$$ or $$$3$$$, but you can do it again on day $$$4$$$.)You are given two integers $$$c$$$ and $$$d$$$. Find the maximum value of $$$k$$$ such that you can gain at least $$$c$$$ coins over $$$d$$$ days. If no such $$$k$$$ exists, output Impossible. If $$$k$$$ can be arbitrarily large, output Infinity.

Input: The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains three integers $$$n,c,d$$$ ($$$2 \leq n \leq 2\cdot10^5$$$; $$$1 \leq c \leq 10^{16}$$$; $$$1 \leq d \leq 2\cdot10^5$$$) — the number of quests, the number of coins you need, and the number of days.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the rewards for the quests.The sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$, and the sum of $$$d$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output: For each test case, output one of the following.   If no such $$$k$$$ exists, output Impossible.  If $$$k$$$ can be arbitrarily large, output Infinity.  Otherwise, output a single integer — the maximum value of $$$k$$$ such that you can gain at least $$$c$$$ coins over $$$d$$$ days.  Please note, the checker is case-sensitive, and you should output strings exactly as they are given.

Note: In the first test case, one way to earn $$$5$$$ coins over $$$4$$$ days with $$$k=2$$$ is as follows:   Day 1: do quest 2, and earn $$$2$$$ coins.  Day 2: do quest 1, and earn $$$1$$$ coin.  Day 3: do nothing.  Day 4: do quest 2, and earn $$$2$$$ coins.  In total, we earned $$$2+1+2=5$$$ coins.In the second test case, we can make over $$$20$$$ coins on the first day itself by doing the first quest to earn $$$100$$$ coins, so the value of $$$k$$$ can be arbitrarily large, since we never need to do another quest.In the third test case, no matter what we do, we can't earn $$$100$$$ coins over $$$3$$$ days.

Sample Inputs:
6
2 5 4
1 2
2 20 10
100 10
3 100 3
7 2 6
4 20 3
4 5 6 7
4 100000000000 2022
8217734 927368 26389746 627896974
2 20 4
5 1

Sample Outputs:
2
Infinity
Impossible
1
12
0

Solution (Python):
t = int(input())
for tt in range(t):
    (n, c, d) = list(map(int, input().split()))
    a = list(map(int, input().split()))
    s = [0]
    a.sort(reverse=True)
    for x in a:
        s.append(s[-1] + x)

    def check(k):
        (kk, rr) = divmod(d, k + 1)
        return kk * s[min(k + 1, n)] + s[min(rr, n)] >= c
    l = 0
    r = d - 1
    while l <= r:
        m = l + r >> 1
        if check(m):
            l = m + 1
        else:
            r = m - 1
    print('Impossible' if r == -1 else r if r != d - 1 else 'Infinity')

Solution (Python):
def f(k, s):
    k += 1
    p = d // k
    q = min(d % k, n)
    total = p * s[min(k, n)] + s[q]
    return total >= c
for _ in range(int(input())):
    (n, c, d) = map(int, input().split())
    a = sorted(list(map(int, input().split())), reverse=True)
    summ = [0 for i in range(n + 1)]
    for i in range(1, n + 1):
        summ[i] = summ[i - 1] + a[i - 1]
    minn = min(d, n)
    if summ[minn] >= c:
        print('Infinity')
    elif a[0] * d < c:
        print('Impossible')
    else:
        up = d
        down = 0
        while up >= down:
            mid = (up + down) // 2
            if f(mid, summ):
                ans = mid
                down = mid + 1
            else:
                up = mid - 1
        print(ans)

Solution (Python):
t = int(input())
for i in range(t):
    (n, c, d) = map(int, input().split())
    l = list(map(int, input().split()))
    l.sort(key=lambda x: -x)
    while len(l) < d:
        l.append(0)
    for i in range(1, d):
        l[i] += l[i - 1]
    hi = d - 1
    lo = -1
    max_k = -1
    while lo < hi:
        mid = (lo + hi + 1) // 2
        sum = l[mid] * (d // (mid + 1))
        if d % (mid + 1):
            sum += l[d % (mid + 1) - 1]
        if sum >= c:
            max_k = max(max_k, mid)
            lo = mid
        else:
            hi = mid - 1
    if max_k == -1:
        print('Impossible')
    elif max_k == d - 1:
        print('Infinity')
    else:
        print(max_k)