← 返回题目列表

Codeforces · 2232/F

F. 蛋糕是一个谎言

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

为了结束聚会,爱丽丝决定为她的朋友们做一些煎饼。

爱丽丝有 $$$n$$$ 未煮过的煎饼,但只有 $$$2$$$ 平底锅。最初,第一个 $$$min(n,2)$$$ 煎饼放在平底锅上,所有煎饼都有熟度 $$$0$$$。

为了煮煎饼,Alice 可以执行以下两个操作任意多次:

  • 将两个煎饼放在平底锅上煮 $$$1$$$ 分钟。第一个锅上的煎饼的熟度增加 $$$a$$$,第二个锅上的煎饼的熟度增加 $$$b$$$。
  • 提供第一个煎饼,将第二个煎饼移到第一个平底锅中,然后将新的未煮熟的煎饼添加到第二个平底锅中(如果还剩下任何完全未煮熟的煎饼)。请注意,这不需要时间,并且可以连续完成多次。

请注意,如果只剩下一个煎饼,它将放在第一个平底锅上,每分钟获得 $$$a$$$ 熟度,直到 Alice 决定提供它。

煎饼完全煮熟当且仅当其熟度恰好为$$$k$$$。

帮助爱丽丝找到她可以提供的最多数量的完全煮熟的煎饼。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

测试用例中唯一的一行包含 $$$4$$$ 整数 $$$n$$$、$$$a$$$、$$$b$$$ 和 $$$k$$$ ($$$1 \le n,a,b,k \le 10^9$$$) — Alice 的煎饼面糊数量、每分钟结束时第一个平底锅上煎饼的熟度、金额第二个平底锅上的煎饼在每分钟结束时获得的熟度,以及煎饼需要完全煮熟的熟度。

输出

对于每个测试用例,输出 Alice 可以制作的完美煮熟的煎饼的最大数量。

示例

输入
复制

7
17 1 1 1
123456789 987 654 321
3 11 37 111111
987654321 1 2 123456789
100 1 2 1
100 1 2 2
1 1 1 1

输出
复制

17
0
2
987654320
50
67
1

注意

在第一个测试用例中,Alice 可以完美地烹饪两个一批的所有煎饼。因此,完美煮熟的煎饼的最大数量为 $$$17$$$。

在第二个测试用例中,爱丽丝总是会把所有煎饼煮过头,因为两个平底锅都太热了。因此,完全煮熟的煎饼的最大数量为 $$$0$$$。

在第三个测试用例中,Alice 可以将前两块煎饼放在平底锅上 $$$3003$$$ 分钟,然后将两块煎饼分别上桌,一个未煮熟,一个完全煮熟。对于最后一块煎饼,她将其放在平底锅上 $$$10\,101$$$ 分钟,然后才上桌,使其完全煮熟。由于没有办法完美地烹饪前两个煎饼(当第一个煎饼完全煮熟时,第二个煎饼就会煮过头),因此完美煮熟的煎饼的最大数量为$$$2$$$。