codeforces-scrape

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

1194D.md (1544B)


      1 Source: https://codeforces.com/problemset/problem/1194/D
      2 
      3 D. 1-2-K Game
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 Alice and Bob play a game. There is a paper strip which is divided into *n* + 1 cells numbered from left to right starting from 0. There is a chip placed in the *n*-th cell (the last one).
     22 
     23 Players take turns, Alice is first. Each player during his or her turn has to move the chip 1, 2 or *k* cells to the left (so, if the chip is currently in the cell *i*, the player can move it into cell *i* - 1, *i* - 2 or *i* - *k*). The chip should not leave the borders of the paper strip: it is impossible, for example, to move it *k* cells to the left if the current cell has number *i* < *k*. The player who can't make a move loses the game.
     24 
     25 Who wins if both participants play optimally?
     26 
     27 Alice and Bob would like to play several games, so you should determine the winner in each game.
     28 
     29 Input
     30 
     31 The first line contains the single integer *T* (1 ≤ *T* ≤ 100) — the number of games. Next *T* lines contain one game per line. All games are independent.
     32 
     33 Each of the next *T* lines contains two integers *n* and *k* (0 ≤ *n* ≤ 109, 3 ≤ *k* ≤ 109) — the length of the strip and the constant denoting the third move, respectively.
     34 
     35 Output
     36 
     37 For each game, print Alice if Alice wins this game and Bob otherwise.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 4  
     45 0 3  
     46 3 3  
     47 3 4  
     48 4 4
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 Bob  
     55 Alice  
     56 Bob  
     57 Alice
     58 ```