CF2255A Hot Potatoes at the Fairy Warehouse

在精灵仓库的一个宁静午后，Ithea 召集了 Chtholly、Nephren 和其它小矮妖们，在晚饭前玩最后一轮游戏：“热土豆”。 有 $2n$ 个小矮妖围成一圈，顺时针编号为 $1$ 到 $2n$。他们被分为两队：所有奇数编号的小矮妖属于红队，偶数编号的小矮妖属于蓝队。 一开始，部分小矮妖手中持有一个土豆。游戏持续 $k$ 轮。 每一轮开始时，双方都已知所有土豆的位置。然后，每一位持有土豆的小矮妖会同时进行如下操作之一： - 保留自己的土豆，或者 - 将土豆递给顺时针方向的下一个小矮妖，但前提是这位下一个小矮妖在本轮开始时并没有土豆。 如果顺时针的下一位小矮妖在本轮开始时已经有了土豆，那么当前持有者必须保留手中的土豆。是否能够递交土豆，仅由每轮开始时的土豆分布决定。 按照上述规则，任何时刻每个小矮妖至多只能持有一个土豆。 当 $k$ 轮全部结束后，最后一声钟响，所有手中还持有土豆的小矮妖都被淘汰。每个队伍的得分定义为本队淘汰对方队员的人数。双方小矮妖都竭尽全力、共享所有可能的信息，以最大化本队得分。 若双方均采取最优策略，求红队与蓝队的得分。 可以保证在最优策略下，得分是唯一确定的。

每个测试点包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1\le n\le 10^5$，$1\le k\le 10^9$），表示小矮妖数量的一半和游戏回合数。 第二行是一个长度为 $2n$ 的二进制字符串 $s$（$s_i=0$ 或 $1$），描述了游戏初始状态。如果 $s_i=1$，说明第 $i$ 个小矮妖最初手里有一个土豆，否则没有。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出两个整数——若双方都采取最优策略时，红队和蓝队的得分。

在第一个测试用例中，最优策略是让 1 号小矮妖把土豆传给 2 号小矮妖（本回合内唯一可能的传递）。最后，只有属于蓝队的 2 号小矮妖手中有土豆。因此，红队得分为 $1$，蓝队得分为 $0$。 在第二个测试用例中，最优策略是 4 号小矮妖将自己的土豆传给 1 号小矮妖。注意，3 号小矮妖不能将土豆递给 4 号小矮妖，因为 4 号小矮妖在本回合开始时已有土豆。 第三个测试用例的示例如下所示：  需要注意的是，这只是对双方最优策略下的一种情况。也可能存在其它最优策略，但无论策略如何，最终的得分都是相同的。 由 ChatGPT 5 翻译