游戏肯定不会无限进行下去。因为当 $$$n\le k$$$ 时 Alice 必须立刻结束游戏，否则 Bob 就会在下一回合移除关键牌来使得分变为 $$$0$$$。而且 Bob 可以一直移除牌来使得牌堆越来越薄。所以 Bob 是有能力阻止 Alice 一直将游戏进行下去的。

首先考虑 $$$s=1$$$ 的情况。这时 Alice 必须决定是拿走关键牌还是把它塞回去。一旦把它塞回去，接下来是谁拿到关键牌就只和它的位置有关。可以发现，只有当 $$$n\equiv k \pmod{2k}$$$ 的时候无论 Alice 怎么塞她都不能在下一次拿到关键牌，此时显然直接移除关键牌最优，否则 Alice 都有办法让自己在下一次拿到这张关键牌，方案是把它放在所有其它取出的牌之前或之后的其中一种，于是塞回去一定比直接移除更优。

从 Alice 把关键牌塞回去这一行动开始，双方会各进行 $$$x=\left\lfloor\frac{n+k}{2k}\right\rfloor$$$ 次操作，然后又会变成 Alice 能够摸到关键牌的情况。关键的是，牌堆的大小会变成多少呢？

设 $$$f_k(n)$$$ 为牌堆大小为 $$$n$$$，$$$s=1$$$，$$$k=k$$$ 时的最终分数。接下来的每次操作中，双方都可以选择移除一张牌或不移除牌。我们可以证明，最后的得分会是 $$$1+\max\left\{\min\{f_k(n-x-1),f_k(n-x)\},\min\{f_k(n-x),f_k(n-x+1)\}\right\}$$$。或者换一种写法，就是，$$$1+\min\{\max\{f_k(n-x-1),f_k(n-x+1)\}, f_k(n-x)\}$$$。

一共有 $$$2x$$$ 次操作，可能会移除 $$$0\sim 2x$$$ 张牌。我们移动一下坐标系，看成，一开始最后会剩 $$$n-x$$$ 张牌。一个人移除牌就相当于减少 $$$0.5$$$ 张牌，不移除就是增加 $$$0.5$$$ 张牌。对于 Alice 来说，她第一步可以选择往左或者往右走 $$$0.5$$$ 步，然后让 Bob 在相邻的两个当中选一个。Bob 一定可以做到他能选中二者之间较小的那个，只要之后他所有操作和 Alice 相反就可以。即最后得分小于等于这个。而 Alice 也一定可以做到让得分大于等于这二者之间较小的那个，因为她可以每次都让 Bob 做一次一模一样的选择。所以答案必须是这个。但是，有一种情况比较特殊：当 $$$n\equiv k+1 \pmod{2k}$$$ 的时候，Alice 为了自己能在下一次摸到关键牌，她必须不移除牌并且将关键牌放在牌堆底。所以这时 Alice 的第一步只有往右走一种选择，于是此时答案变成了 $$$1+\min\left\{ f_k(n-\left\lfloor\frac{n+k}{2k}\right\rfloor), f_k(n-\left\lfloor\frac{n+k}{2k}\right\rfloor+1) \right\}$$$。

然后，这道题有一个有趣的性质（我是打表发现的），就是当 $$$f_k(n-1) \lt f_k(n) \gt f_k(n+1)$$$ 的时候，必有 $$$n\equiv k-1 \pmod{2k}$$$。证明也不难。考虑以 $$$n\equiv k \pmod{2k}$$$ 的位置分段。对于 $$$n-1,n,n+1$$$ 在同一段之间（即不包含这些值为 $$$1$$$ 的点）的情况，设 $$$f_k(n-1)=\max\{[m_{12},]m_{23}\},f_k(n)=\max\{m_{23},m_{34}\},f_k(n+1)=\max\{m_{34},m_{45}\}$$$。其中 $$$m_{ij}$$$ 表示 $$$f_k$$$ 的相邻两项的最小值加 $$$1$$$。如果有 $$$m_{23}\ge m_{34}$$$ 那么就有 $$$f_k(n-1)\ge f_k(n)$$$（无论 $$$m_{12}$$$ 这一项是否存在），如果有 $$$m_{23} \lt m_{34}$$$ 那么就有 $$$f_k(n+1)\ge f_k(n)$$$。当 $$$n\equiv k+1$$$ 的时候，$$$f_k(n-1)=1,f_k(n)=m_{34},f_k(n+1)=\max\{m_{34},m_{45}\}\ge f_k(n)$$$。当 $$$n\equiv k$$$ 时 $$$f_k(n)=1$$$ 一定不会大于两边。所以，当 $$$f_k(n-1) \lt f_k(n) \gt f_k(n+1)$$$ 的时候，必有 $$$n\equiv k-1 \pmod{2k}$$$。此时 $$$f_k(n+1)=1$$$。

所以说，只要不是 $$$n\equiv k,n\equiv k+1, n-x\equiv k-1$$$ 三种情况，都有 $$$f_k(n)=f_k(n-x)+1$$$。对于其中的第三种情况，由于 $$$f_k(n-x-1)$$$ 一定大于等于 $$$f_k(n-x+1)=1$$$，所以可以写成 $$$1+\min\left\{ f_k(n-\left\lfloor\frac{n+k}{2k}\right\rfloor), f_k(n-\left\lfloor\frac{n+k}{2k}\right\rfloor-1) \right\}$$$。于是就有了下面的递推式：

$$$f_k(n)=\begin{cases}1, & n \equiv k \pmod{2k} \\ 1+\min\left\{f_k\left(n-\left\lfloor\frac{n+k}{2k}\right\rfloor\right), f_k\left(n-\left\lfloor\frac{n+k}{2k}\right\rfloor+1\right)\right\}, & n\equiv k+1 \pmod{2k} \\ 1+\min\left\{ f_k\left(n-\left\lfloor\frac{n+k}{2k}\right\rfloor\right), f_k\left(n-\left\lfloor\frac{n+k}{2k}\right\rfloor-1\right) \right\}, & n \equiv k-1+\left\lfloor\frac{n+k}{2k}\right\rfloor \not\equiv k+1 \pmod{2k} \\ 1+f_k(n-\left\lfloor\frac{n+k}{2k}\right\rfloor), & \text{otherwise}\end{cases}$$$

注意到当 $$$k$$$ 比较大的时候 $$$x$$$ 很小，所以对于最后一种情况，可以在 $$$x$$$ 相同的地方加速一下。也就是考虑连续跳 $$$\left\lfloor\frac{(n+k) \bmod 2k}{x}\right\rfloor$$$ 步。显然途中不会经过前三种情况。如果这个值是 $$$0$$$，那么就正常跳一步。

接下来考虑 $$$s\ne 1$$$ 的情况。也就是说，距离关键牌浮出表面，双方还要各行动 $$$x=\left\lfloor\frac{s-1}{2k}\right\rfloor$$$ 次。 于是按照之前的分析，答案就是 $$$\min\{\max\{f_k(n-x-1),f_k(n-x+1)\}, f_k(n-x)\}$$$。

递推式用记忆化搜索即可。因为 $$$n\equiv k$$$ 时立刻返回 $$$1$$$，$$$n\equiv k+1$$$ 时会向后扩展，遇到 $$$n\equiv k-1$$$ 会向前扩展，所以每一层下来最多只有两个状态会被访问。在 $$$n\le (2k)^2$$$ 时有 $$$x\le 2k$$$ 且因为加速了最后一行所以只有 $$$\min\{n,(2k)^2\}\over 2k$$$ 层，在 $$$n \gt (2k)^2$$$ 的时候每次 $$$n$$$ 会变成原来的 $$$2k-1\over 2k$$$，所以有 $$$2k\max\{0,\log(n/(2k)^2)\}$$$ 层。前者在 $$$k=\sqrt{n}/2$$$ 时取最大值，后者在 $$$k=\sqrt{n}/2e$$$ 时取最大值，均为 $$$O(\sqrt{n})$$$。