← 返回题目列表

Codeforces · 1760/F

F. 任务

中文机器翻译题面 查看原题

有 $$$n$$$ 任务。如果您完成第 $$$i$$$ 个任务,您将获得 $$$a_i$$$ 硬币。您每天最多只能完成一项任务。但是,一旦完成任务,您就无法在 $$$k$$$ 天内再次执行相同的任务。 (例如,如果 $$$k=2$$$ 并且您在 $$$1$$$ 天执行了任务 $$$1$$$,那么您无法在 $$$2$$$ 或 $$$3$$$ 天执行任务,但您可以在 $$$4$$$ 天再次执行任务。)

给你两个整数 $$$c$$$ 和 $$$d$$$。找到 $$$k$$$ 的最大值,这样您就可以在 $$$d$$$ 天内获得至少 $$$c$$$ 硬币。如果不存在这样的$$$k$$$,则输出Impossible。如果 $$$k$$$ 可以任意大,则输出 Infinity。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n,c,d$$$ ($$$2 \leq n \leq 2\cdot10^5$$$; $$$1 \leq c \leq 10^{16}$$$; $$$1 \leq d \leq 2\cdot10^5$$$) — 任务数量,数量您需要的硬币数量以及天数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 任务的奖励。

所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$,所有测试用例的 $$$d$$$ 总和不超过 $$$2\cdot10^5$$$。

输出

对于每个测试用例,输出以下内容之一。

- 如果不存在这样的 $$$k$$$ ,则输出 Impossible。
- 如果 $$$k$$$ 可以任意大,则输出 Infinity。
- 否则,输出一个整数 - $$$k$$$ 的最大值,这样您就可以在 $$$d$$$ 天内获得至少 $$$c$$$ 硬币。

示例

输入 #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

注意

在第一个测试用例中,在 $$$4$$$ 天内赚取 $$$5$$$ 硬币($$$k=2$$$)的一种方法如下:

- 第 1 天:完成任务 2,并赚取 $$$2$$$ 硬币。
- 第 2 天:完成任务 1,并赚取 $$$1$$$ 硬币。
- 第三天:什么也不做。
- 第 4 天:完成任务 2,赚取 $$$2$$$ 硬币。

在第二个测试用例中,我们可以通过执行第一个任务在第一天赚取超过 $$$20$$$ 硬币来赚取 $$$100$$$ 硬币,因此 $$$k$$$ 的值可以是任意大,因为我们永远不需要做另一个任务。

在第三个测试用例中,无论我们做什么,我们都无法在 $$$3$$$ 天内赚取 $$$100$$$ 硬币。