If a player is left with a single rock in the pile, they lose immediately since they have no choice but to take that last rock. Therefore, having ~1~ rock is a "losing position".

This means that if a player is able to place the other player in this losing position, they can force the other player to take this losing position, and they themselves win. Therefore, ~2, \ldots, 1+K~ are all "winning positions".

A player who is unable to place the other player in a losing position will be in a losing position since any move they make will put the other player in a winning position.

Thus, the concept of game theory is that once all a player's options are explored, if any of them puts the other player in a "losing position", then the current state is a "winning position" for them. If no move exists that forces the other player into a losing position, that state is a "losing position" for them.

Here is a solution to the problem using recursion and memoization (saving previous calculated states) to determine the state of ~N~.

Time complexity: ~\mathcal{O}(NK)~.

N, K = map(int, input().split())
state = [None] * (N + 1) # True for a winning state, False for a losing state
state[0] = True; state[1] = False # Base cases: 0 stones is a winning state, and 1 stone is a losing state

def get_state(m): # Computes the winning/losing state of being given m stones
    if not state[m] is None: # If this state has already been calculated, simply return it
        return state[m]
    for take in range(1, K + 1):
        # Check to see that we can force a losing state onto the other player
        if m - take >= 0 and get_state(m - take) == False:
            state[m] = True
            return True # If so, this is a winning state
    state[m] = False
    return False

print(":hudab:" if get_state(N) else "baf")

For subtask 1, notice the pattern that emerges from the calculated states: ~1~ stone is losing, then the next ~K~ are winning, the next is losing, the next ~K~ are winning, and so on.

Time complexity: ~\mathcal{O}(N)~.

For Subtask 2, use mod to quickly find the answer from the pattern: if ~N-1~ is a multiple of ~K+1~, it is a losing state. All other states are winning states.

Time complexity: ~\mathcal{O}(1)~.

N, K = map(int, input().split())
print("baf" if (N - 1) % (K + 1) == 0 else ":hudab:")