2184D.md (2623B)
1 Source: https://codeforces.com/problemset/problem/2184/D 2 3 D. Unfair Game 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Bob is tired of losing to Alice and, to ensure he doesn't lose again, decided to choose a game in which he is guaranteed to win. Bob has thought of a number from $1$ to $n$, where it is known that $n = 2^d$ for some non-negative integer $d$. Initially, Alice knows whether the chosen number is even or not. 22 23 In one move, Alice can either halve the number or subtract $1$. Alice can only halve the number if the current number is even. Only Alice takes turns. 24 25 After her move, Alice receives a response from Bob: either $-1$, which means the number has become $0$ and Alice has won, or a non-negative integer $x$. If we denote the current number as $a$, then for $x$ the following conditions hold simultaneously: 26 27 1. $a$ is divisible by $2^x$. 28 2. $a$ is not divisible by $2^{x+1}$. 29 30 For example, if $a=5$, then $x=0$, since $5$ is divisible by $2^0=1$ and not divisible by $2^1=2$, and if $a=12$, then $x=2$, since $12$ is divisible by $2^2=4$ and not divisible by $2^3=8$. 31 32 It can be shown that for any integer $a \gt 0$, there exists a unique such $x$. 33 34 Bob is still afraid that Alice will win, so the game will have no more than $k$ moves. Additionally, Bob wants to maximize his chances of winning, so he wants to play as many games as possible. Given $n$ and $k$, calculate the number of initial numbers from $1$ to $n$ such that Alice, playing optimally, cannot win in no more than $k$ moves. 35 36 Input 37 38 The first line contains an integer $t$ $(1 \le t \le 10^4)$ — the number of test cases. 39 40 The only line of each test case contains $2$ integers $n$ and $k$ $(1 \le n, k \le 10^9)$ — the limit on the chosen number and the maximum number of Alice's moves, respectively. It is guaranteed that $n = 2^d$ for some non-negative integer $d$. 41 42 Output 43 44 For each test case, output the number of integers from $1$ to $n$ such that Alice, playing optimally, cannot win in at most $k$ moves. 45 46 Example 47 48 Input 49 50 ``` 51 7 52 53 4 1 54 55 4 2 56 57 4 3 58 59 4 4 60 61 4 5 62 63 16 5 64 65 16 1 66 ``` 67 68 Output 69 70 ``` 71 3 72 73 2 74 75 0 76 77 0 78 79 0 80 81 4 82 83 15 84 ``` 85 86 Note 87 88 In the first sample, $a=2$, $a=3$, and $a=4$ are suitable because from $a=1$ one can reach $0$ in $1$ operation, while for the other values, it can be shown that at least $2$ operations are required. 89 90 In the second sample, $a=3$ and $a=4$ are suitable because for $a=2$, Alice can win in $2$ operations. 91 92 In the third, fourth, and fifth samples, there are no suitable $a$, because for $a=3$ and $a=4$, Alice can win in $3$ operations.