codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.