P15035 [UOI 2021 II Stage] Game

Double experience: .

Cossack Moustache has come up with another problem for competitive programmers. You are given a set of $n$ strings $s_1, s_2, \ldots, s_n$ and a number $k$. A set of strings is called **beautiful** if and only if: - Each string consists only of $0$ and $1$; - The length of each string is at most $k$; - No string is a prefix of another string. The given set is **beautiful**. Alice and Bob are playing the following game. They take turns to make a move. In each move, they may add a string to the set, provided that after adding it, the set is still **beautiful**. The player who cannot make a move loses. Alice moves first. Help determine who will win if both players play optimally.

The first line contains two integers $n$ ($0 \le n \le 10^5, 1 \le k \le 10^{18}$), which are the number of strings in the set and the maximum allowed length of strings in a beautiful set. The next $n$ lines follow. The $i$-th line contains a string $s_i$ ($1 \le |s_i| \le 10^6$). It is guaranteed that $\sum_{i=1}^{n}{|s_i|} \le 10^6$. It is also guaranteed that the initial set is **beautiful**.

If Alice wins, output Alice. If Bob wins, output Bob.

### Scoring - (2 points): $n = 0$. - (6 points): $k = 2$. - (8 points): $k = 3$. - (12 points): $k \le 10$. - (17 points): $k \le 20$. - (20 points): $k \le 10^4$. - (35 points): No additional constraints. Translated by ChatGPT 5