Боб устал проигрывать Алисе и, чтобы точно больше не проиграть, решил выбрать игру так, чтобы гарантированно победить. Боб загадал число от $$$1$$$ до $$$n$$$, причем известно, что $$$n = 2^d$$$ для некоторого целого неотрицательного числа $$$d$$$. Изначально Алисе известно, чётное загаданное число или нет.
За одно действие Алиса может либо уменьшить его вдвое, либо вычесть $$$1$$$. Уменьшить число вдвое Алиса может только в том случае, если текущее число чётное. Ходит только Алиса.
После своего действия Алиса получает от Боба ответ: либо $$$-1$$$, что означает, что число стало равно $$$0$$$, и Алиса выиграла, либо неотрицательное целое число $$$x$$$. Если обозначить текущее число за $$$a$$$, то для $$$x$$$ одновременно выполнены условия:
Например, если $$$a=5$$$, то $$$x=0$$$, так как $$$5$$$ делится на $$$2^0=1$$$ и не делится на $$$2^1=2$$$, а если $$$a=12$$$, то $$$x=2$$$, так как $$$12$$$ делится на $$$2^2=4$$$ и не делится на $$$2^3=8$$$.
Можно показать, что для любого целого $$$a \gt 0$$$ существует единственное такое $$$x$$$.
Боб всё-таки боится, что Алиса выиграет, поэтому в игре будет не более $$$k$$$ ходов. Также Боб хочет отыграться по максимуму, поэтому он хочет сыграть как можно больше игр. По заданным $$$n$$$ и $$$k$$$ посчитайте количество изначальных чисел от $$$1$$$ до $$$n$$$ таких, что Алиса, играя оптимально, не сможет выиграть не более чем за $$$k$$$ ходов.
В первой строке содержится целое число $$$t$$$ $$$(1 \le t \le 10^4)$$$ — количество наборов входных данных.
В единственной строке каждого набора входных данных содержатся $$$2$$$ целых числа $$$n$$$ и $$$k$$$ $$$(1 \le n, k \le 10^9)$$$ — ограничение на загаданное число и максимальное количество ходов Алисы соответственно. Гарантируется, что $$$n = 2^d$$$ для некоторого целого неотрицательного числа $$$d$$$.
Для каждого набора входных данных выведите количество чисел от $$$1$$$ до $$$n$$$ таких, что Алиса, играя оптимально, не сможет победить не более чем за $$$k$$$ ходов.
74 14 24 34 44 516 516 1
32000415
В первом примере подходят $$$a=2$$$, $$$a=3$$$ и $$$a=4$$$, так как из $$$a=1$$$ можно попасть в $$$0$$$ за $$$1$$$ операцию, а для остальных значений можно показать, что потребуется хотя бы $$$2$$$ операции.
Во втором примере подходят $$$a=3$$$ и $$$a=4$$$, так как при $$$a=2$$$ Алиса может выиграть за $$$2$$$ операции.
В третьем, четвертом и пятом примерах нет подходящих $$$a$$$, так как для $$$a=3$$$ и $$$a=4$$$ Алиса может выиграть за $$$3$$$ операции.
| Codeforces Round 1072 (Div. 3) |
|---|
| Закончено |
