1-2-K Game (Codeforces 1194D)
Tags: Math, games

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).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.Who wins if both participants play optimally?Alice and Bob would like to play several games, so you should determine the winner in each game.

Input: 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.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.

Output: For each game, print Alice if Alice wins this game and Bob otherwise.


Sample Inputs:
4
0 3
3 3
3 4
4 4

Sample Outputs:
Bob
Alice
Bob
Alice

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().split())
    if k % 3 != 0:
        if n % 3 == 0:
            print('Bob')
        else:
            print('Alice')
    elif k % 3 == 0:
        k += 1
        if n % k % 3 == 0 and n % k != k - 1:
            print('Bob')
        else:
            print('Alice')

Solution (Python):
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    if k % 3:
        print(n % 3 and 'Alice' or 'Bob')
    else:
        n %= k + 1
        print((n == k or n % 3) and 'Alice' or 'Bob')

Solution (Python):
t = int(input())
for _ in range(0, t):
    inputs = [int(num) for num in input().split()]
    n = inputs[0]
    k = inputs[1]
    if k % 3 == 0:
        pos = n % (k + 1)
        if pos % 3 == 0:
            if pos == k:
                print('Alice')
            else:
                print('Bob')
        else:
            print('Alice')
    elif n % 3 == 0:
        print('Bob')
    else:
        print('Alice')