#K66392. Determine the Winner of the Missing Number Game
Determine the Winner of the Missing Number Game
Determine the Winner of the Missing Number Game
In this game, two players, Alice and Bob, take turns appending a number to a sequence. The game rules are as follows:
-
You are given two integers (m) and (n), where (m) denotes the maximum integer available (the numbers available are from 1 to (m)), and (n) denotes the current number of integers in the sequence.
-
You are also given a sequence of (n) integers. The sequence may or may not contain all numbers from 1 to (m).
-
On each turn, the current player must add one integer from the range [1, (m)] that is not already in the sequence. Alice always makes the first move.
-
If at the start of a turn the sequence already contains all (m) distinct numbers (i.e. (|\text{sequence}| = m)), then the current player cannot make a move and loses the game.
It can be proven that if there is at least one number missing from the sequence (i.e. (|\text{sequence}| < m)), then the first player (Alice) can always force a win. Otherwise, if the sequence is complete ((|\text{sequence}| = m)), then Bob wins by default.
Your task is to determine the winner of the game given (m), (n), and the initial sequence.
inputFormat
The input is given via standard input (stdin) and consists of two lines:
- The first line contains two space-separated integers (m) and (n) where (1 \leq m \leq 10^5) and (0 \leq n \leq m).
- The second line contains (n) space-separated integers representing the initial sequence. If (n = 0), this line is empty.
outputFormat
Output to standard output (stdout) a single line containing either "Alice" or "Bob" depending on who wins the game.## sample
10 3
1 2 3
Alice