研究:从面朝下的等级牌组中抽一张牌,数量等于你的研究量。您可以选择 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$$$)。
输出
对于每个测试用例,如果游戏永远不会结束,则输出一行带有单词 无穷大;否则,输出一个整数——游戏的得分。
示例
输入复制
63 2 15 3 410 3 17 3 7817247666 7237 327476688610723117 332458760 292738094
输出复制
20243470278264358
注意
在第一个测试用例中,游戏的最优流程如下。 Alice 应该从顶部取出 $$$2$$$ 卡,不丢弃任何内容,并将绿卡放回到这副牌的底部。然后鲍勃应该从顶部取出 $$$2$$$ 白牌并丢弃一张。在第三回合,爱丽丝应该丢弃上面写有数字 $$$2$$$ 的绿卡。
在第二个测试用例中,Bob 将首先拿走绿卡并将其丢弃。因此,分数应该是$$$0$$$。