Quests
Contest: Codeforces Round 835 (Div. 4)
Difficulty rating: 1500
Tags: binary search, 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 format:
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 format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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

Example input:
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

Example output:
2
Infinity
Impossible
1
12
0

Editorial:
Let's fix $$$k$$$ and find the maximum number of coins we can get. Here we can do a greedy solution: at every step, we should always take the most rewarding quest. (Intuitively, it makes sense, since doing more rewarding quests earlier allows us to do them again later.) If no quests are available, we do nothing.
To implement this, sort the quests in decreasing order, and $$$0$$$-index them. On day $$$i$$$ we should do quest $$$i \bmod k$$$, provided that this value is less than $$$n$$$. This is because after every $$$k$$$ days, we cycle back to the first quest. Thus we solved the problem for a fixed $$$k$$$ in $$$\mathcal{O}(d)$$$ with $$$\mathcal{O}(n \log n)$$$ precomputation to sort the array.
Now to solve the problem, we can binary search on the answer, since if some $$$k$$$ works, then all smaller $$$k$$$ work. The minimum value of $$$k$$$ is $$$0$$$, and the maximum value is $$$n$$$ (for larger $$$k$$$, we won't be able to do the same quest multiple times anyways, so it's useless to consider them).
If we find that $$$k$$$ always goes towards the smaller end of our binary search and $$$k=0$$$ still fails, we output Impossible. If we find that $$$k$$$ always goes towards the larger end of our binary search and $$$k=n$$$ still fails, we output Infinity. Otherwise, just output $$$k$$$.
The overall time complexity is $$$\mathcal{O}(n \log n + d \log n)$$$.
Remark. It is not hard to improve the solution to $$$\mathcal{O}(n \log n)$$$. Originally, I proposed the problem this way, but we ended up removing this part of the problem because the implementation of this solution was tricky enough.