← 返回题目列表

Codeforces · 2184/D

D. 不公平的游戏

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

Bob 厌倦了输给 Alice,为了确保他不会再输,决定选择一场保证他获胜的游戏。 Bob 想到了从 $$$1$$$ 到 $$$n$$$ 的数字,其中已知对于某个非负整数 $$$d$$$,$$$n = 2^d$$$。最初,爱丽丝 知道 所选数字是否为偶数。

在一步中,Alice 可以将数字减半或减去 $$$1$$$。如果当前数字是偶数,爱丽丝只能将数字减半。只有爱丽丝轮流。

移动后,Alice 收到 Bob 的回复:要么是 $$$-1$$$,这意味着数字变成了 $$$0$$$ 并且 Alice 赢了,要么是一个非负整数 $$$x$$$。如果我们将当前数字表示为$$$a$$$,那么对于$$$x$$$,以下条件同时成立:

  1. $$$a$$$ 可以被 $$$2^x$$$ 整除。
  2. $$$a$$$ 不能被 $$$2^{x+1}$$$ 整除。

例如,如果 $$$a=5$$$,则 $$$x=0$$$,因为 $$$5$$$ 可被 $$$5$$$ 整除,且不能被 $$$2^1=2$$$ 整除,如果 $$$a=12$$$,则 $$$x=2$$$,因为 $$$12$$$ 可被 $$$12$$$ 整除$$$2^2=4$$$ 且不能被 $$$2^3=8$$$ 整除。

可以证明,对于任何整数$$$a \gt 0$$$,都存在唯一的$$$x$$$。

Bob 仍然担心 Alice 会赢,因此游戏的步数不会超过 $$$k$$$。此外,鲍勃希望最大化他获胜的机会,因此他想玩尽可能多的游戏。给定 $$$n$$$ 和 $$$k$$$,计算从 $$$1$$$ 到 $$$n$$$ 的初始数字的数量,这样爱丽丝在最佳状态下,在不超过 $$$k$$$ 的移动中无法获胜。

输入

第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 测试用例的数量。

每个测试用例的唯一行包含 $$$2$$$ 整数 $$$n$$$ 和 $$$k$$$ $$$(1 \le n, k \le 10^9)$$$ — 分别是所选数字的限制和 Alice 移动的最大数量。对于某些非负整数 $$$d$$$,保证 $$$n = 2^d$$$。

输出

对于每个测试用例,输出从 $$$1$$$ 到 $$$n$$$ 的整数个数,这样 Alice 在最佳状态下最多无法在 $$$k$$$ 步中获胜。

示例

输入
复制

7
4 1
4 2
4 3
4 4
4 5
16 5
16 1

输出
复制

3
2
0
0
0
4
15

注意

在第一个示例中,$$$a=2$$$、$$$a=3$$$ 和 $$$a=4$$$ 是合适的,因为从 $$$a=1$$$ 可以在 $$$1$$$ 操作中到达 $$$0$$$,而对于其他值,可以表明至少需要 $$$2$$$ 操作。

在第二个示例中,$$$a=3$$$ 和 $$$a=4$$$ 是合适的,因为对于 $$$a=2$$$,Alice 可以在 $$$2$$$ 操作中获胜。

在第三个、第四个和第五个样本中,没有合适的$$$a$$$,因为对于$$$a=3$$$和$$$a=4$$$,Alice可以在$$$3$$$操作中获胜。