Alphonso vs Beatrice: The Stone Game

In this strategic two-player game, players take turns removing stones from a pile. On each turn, a player may remove either 1, 3, or 4 stones. Both players play optimally. Given an initial number of stones \(n\), determine whether Alphonso can guarantee a win or if Beatrice can force a win.

Formally, let \(dp[i]\) be true if the current player can force a win with \(i\) stones remaining. The recurrence is given by:

[ dp[i] = \begin{cases} \text{true} & \text{if } (i \ge 1 \text{ and } !dp[i-1]) \text{ or } (i \ge 3 \text{ and } !dp[i-3]) \text{ or } (i \ge 4 \text{ and } !dp[i-4]) \ \text{false} & \text{otherwise} \end{cases} ]

Your task is to implement a program that, given \(n\) read from standard input, prints "Alphonso" if Alphonso can guarantee a win, or "Beatrice" otherwise.

inputFormat

The input consists of a single integer \(n\) (\(0 \le n \le 10^6\)), representing the initial number of stones in the pile. The input is read from stdin.

outputFormat

Output a single line to stdout containing either "Alphonso" or "Beatrice" depending on who can guarantee a win when both players play optimally.

2

Beatrice