Quests

题意翻译

有 $n$ 个任务，你每一天都可以选择其中的一个任务完成或不选。当你完成了第 $i$ 个任务，你将获得 $a_i$ 元。但是如果你今天完成了一个任务，那么你之后 $k$ 天内都不能再完成这个任务。 给出两个数 $c$，$d$，要求求出满足在 $d$ 天内可以收集至少 $c$ 元的最大的 $k$。 如果不存在这样的 $k$，输出 Impossible。 如果 $k$ 可以无限大，输出 Infinity。 否则输出最大的 $k$。

题目描述

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.

输入输出格式

输入格式

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

输出格式

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.

输入输出样例

输入样例 #1

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

输出样例 #1

2
Infinity
Impossible
1
12
0

说明

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.

**题目大意：**
有 $ n $ 个任务，每天可以选择完成一个任务或不做任务。完成第 $ i $ 个任务可以获得 $ a_i $ 元。但是，如果某天完成了某个任务，那么接下来的 $ k $ 天内不能再次完成这个任务。给定两个数 $ c $ 和 $ d $，要求求出满足在 $ d $ 天内可以收集至少 $ c $ 元的最大的 $ k $。

如果不存在这样的 $ k $，输出 "Impossible"。

如果 $ k $ 可以无限大，输出 "Infinity"。

否则输出最大的 $ k $。

**输入输出数据格式：**

**输入格式：**
第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含三个整数 $ n, c, d $（$ 2 \leq n \leq 2 \times 10^5 $；$ 1 \leq c \leq 10^{16} $；$ 1 \leq d \leq 2 \times 10^5 $），分别表示任务的数量、需要收集的硬币数量和天数。

每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $（$ 1 \leq a_i \leq 10^9 $），分别表示任务的奖励。

所有测试用例中 $ n $ 的总和不超过 $ 2 \times 10^5 $，$ d $ 的总和不超过 $ 2 \times 10^5 $。

**输出格式：**
对于每个测试用例，输出以下内容之一：

- 如果不存在这样的 $ k $，输出 "Impossible"。
- 如果 $ k $ 可以无限大，输出 "Infinity"。
- 否则，输出一个整数，表示在 $ d $ 天内可以收集至少 $ c $ 元的最大的 $ k $。

请注意，检查器对大小写敏感，并且应该严格按照给定的格式输出字符串。

**输入输出样例：**

**输入样例 #1：**
```
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
```

**输出样例 #1：**
```
2
Infinity
Impossible
1
12
0
```**题目大意：** 有 $ n $ 个任务，每天可以选择完成一个任务或不做任务。完成第 $ i $ 个任务可以获得 $ a_i $ 元。但是，如果某天完成了某个任务，那么接下来的 $ k $ 天内不能再次完成这个任务。给定两个数 $ c $ 和 $ d $，要求求出满足在 $ d $ 天内可以收集至少 $ c $ 元的最大的 $ k $。 如果不存在这样的 $ k $，输出 "Impossible"。 如果 $ k $ 可以无限大，输出 "Infinity"。 否则输出最大的 $ k $。 **输入输出数据格式：** **输入格式：** 第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含三个整数 $ n, c, d $（$ 2 \leq n \leq 2 \times 10^5 $；$ 1 \leq c \leq 10^{16} $；$ 1 \leq d \leq 2 \times 10^5 $），分别表示任务的数量、需要收集的硬币数量和天数。 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $（$ 1 \leq a_i \leq 10^9 $），分别表示任务的奖励。 所有测试用例中 $ n $ 的总和不超过 $ 2 \times 10^5 $，$ d $ 的总和不超过 $ 2 \times 10^5 $。 **输出格式：** 对于每个测试用例，输出以下内容之一： - 如果不存在这样的 $ k $，输出 "Impossible"。 - 如果 $ k $ 可以无限大，输出 "Infinity"。 - 否则，输出一个整数，表示在 $ d $ 天内可以收集至少 $ c $ 元的最大的 $ k $。 请注意，检查器对大小写敏感，并且应该严格按照给定的格式输出字符串。 **输入输出样例：** **输入样例 #1：** ``` 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 ``` **输出样例 #1：** ``` 2 Infinity Impossible 1 12 0 ```