← 返回题目列表

Codeforces · 2215/F

F. 研究

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

研究:从面朝下的等级牌组中抽一张牌,数量等于你的研究量。您可以选择 1 进行构建或归档。

Alice 和 Bob 将用一副纸牌玩游戏。这副牌由 $$$n-1$$$ 白牌和一张绿牌组成。最初,绿卡位于从牌堆顶部算起的第 $$$s$$$ 位置,上面写着数字 $$$1$$$。 Alice 和 Bob 都知道绿卡的位置。

爱丽丝先走。在每一轮中,他们应该按如下方式进行:

  • 从牌堆顶部取出 $$$k$$$ 卡。 (如果牌组中的牌少于$$$k$$$,则将其全部拿走。)之后,丢弃这些$$$k$$$牌中的$$$0$$$或$$$1$$$牌,并将剩余的牌按照他们喜欢的顺序放在牌组的底部。
  • 如果绿卡被 Bob 丢弃,游戏立即结束,得分为 $$$0$$$。
  • 如果绿卡被爱丽丝丢弃,游戏立即结束,得分等于绿卡上写的数字。
  • 如果 Alice 拿走绿卡并将其放回牌堆,她应该告诉 Bob 绿卡的新位置,并将绿卡上的数字增加 $$$1$$$。

Alice 需要最大化分数,而 Bob 需要最小化分数。如果双方都发挥最佳,您必须找到游戏的最终得分。

输入

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

每个测试用例的唯一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$s$$$ ($$$1\le n,k\le 10^9$$$, $$$1\le s\le n$$$)。

输出

对于每个测试用例,如果游戏永远不会结束,则输出一行带有单词 无穷大;否则,输出一个整数——游戏的得分。

示例

输入
复制

6
3 2 1
5 3 4
10 3 1
7 3 7
817247666 7237 327476688
610723117 332458760 292738094

输出
复制

2
0
2
4
3470
278264358

注意

在第一个测试用例中,游戏的最优流程如下。 Alice 应该从顶部取出 $$$2$$$ 卡,不丢弃任何内容,并将绿卡放回到这副牌的底部。然后鲍勃应该从顶部取出 $$$2$$$ 白牌并丢弃一张。在第三回合,爱丽丝应该丢弃上面写有数字 $$$2$$$ 的绿卡。

在第二个测试用例中,Bob 将首先拿走绿卡并将其丢弃。因此,分数应该是$$$0$$$。