A Game With Numbers
Contest: Codeforces Round 460 (Div. 2)
Difficulty rating: 2600
Tags: games, graphs, shortest paths

Imagine that Alice is playing a card game with her friend Bob. They both have exactly $$$8$$$ cards and there is an integer on each card, ranging from $$$0$$$ to $$$4$$$. In each round, Alice or Bob in turns choose two cards from different players, let them be $$$a$$$ and $$$b$$$, where $$$a$$$ is the number on the player's card, and $$$b$$$ is the number on the opponent's card. It is necessary that $$$a \cdot b \ne 0$$$. Then they calculate $$$c = (a + b) \bmod 5$$$ and replace the number $$$a$$$ with $$$c$$$. The player who ends up with numbers on all $$$8$$$ cards being $$$0$$$, wins.

Now Alice wants to know who wins in some situations. She will give you her cards' numbers, Bob's cards' numbers and the person playing the first round. Your task is to determine who wins if both of them choose the best operation in their rounds.

Input format:
The first line contains one positive integer $$$T$$$ ($$$1 \leq T \leq 100\,000$$$), denoting the number of situations you need to consider.

The following lines describe those $$$T$$$ situations. For each situation:

- The first line contains a non-negative integer $$$f$$$ ($$$0 \leq f \leq 1$$$), where $$$f = 0$$$ means that Alice plays first and $$$f = 1$$$ means Bob plays first.
- The second line contains $$$8$$$ non-negative integers $$$a_1, a_2, \ldots, a_8$$$ ($$$0 \leq a_i \leq 4$$$), describing Alice's cards.
- The third line contains $$$8$$$ non-negative integers $$$b_1, b_2, \ldots, b_8$$$ ($$$0 \leq b_i \leq 4$$$), describing Bob's cards.

We guarantee that if $$$f=0$$$, we have $$$\sum_{i=1}^{8}a_i \ne 0$$$. Also when $$$f=1$$$, $$$\sum_{i=1}^{8}b_i \ne 0$$$ holds.

Output format:
Output $$$T$$$ lines. For each situation, determine who wins. Output

- "Alice" (without quotes) if Alice wins.
- "Bob" (without quotes) if Bob wins.
- "Deal" (without quotes) if it gets into a deal, i.e. no one wins.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first situation, Alice has all her numbers $$$0$$$. So she wins immediately.

In the second situation, Bob picks the numbers $$$4$$$ and $$$1$$$. Because we have $$$(4 + 1) \bmod 5 = 0$$$, Bob wins after this operation.

In the third situation, Alice picks the numbers $$$1$$$ and $$$4$$$. She wins after this operation.

In the fourth situation, we can prove that it falls into a loop.

Example input:
4
1
0 0 0 0 0 0 0 0
1 2 3 4 1 2 3 4
1
0 0 0 1 0 0 0 0
0 0 0 0 4 0 0 0
0
1 0 0 0 0 0 0 0
0 0 0 4 0 0 2 0
1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

Example output:
Alice
Bob
Alice
Deal

Editorial:
First we should notice that the useful number of states isn't something like $$$(8^5)^2$$$, because the order of the numbers in each player's hand does not matter. Therefore, the useful states of each player is $$$\binom{5 + 8 - 1}{8}$$$. Then the useful states is estimated as $$$\binom{5 + 8 - 1}{8}^2$$$, which is $$$245\,025$$$.
Then we can abstract those states as nodes, then link those nodes with directed edges which shows the transformation between two states (i.e. one can make one step to the other). Then we run BFS (or topological sort) on that graph. For a certain state, if all states it links out:
1. has a state that the current player will win. Then the current player will win.
2. has a state that the will get into a deal. Then the current player will make it deal.
3. are all lose states. Then the current player will lose.
It is because the current player can choose the best way to go.
So we can do some initialization to get the "Win", "Lose" or "Deal" status for all possible states. Follow these steps shown below.
1. Give all states that is easily to identify a status "Win" or "Lose". Then push them into a queue. For other states, give "Deal" temporarily.
2. Take a state from the front of the queue. Update all states that can reach this state in one step (i.e. has an edge between them) using the rule shown above.
3. If the state can be defined as one status, push it into the queue and go to the second step. Or you can ignore it and go to the second step instantly.
After this step (or we can say "Initialization"), we can answer those $$$T$$$ queries easily.
Time complexity: $$$\mathcal{O}(k^2 \cdot \binom{m + k - 1}{k}^2 + T)$$$, where $$$k$$$ is the card number one player has, and $$$m$$$ is the modulo. Here we have $$$m = 5$$$ and $$$k = 8$$$.
Bonus: Can you prove that the useful state of each player is $$$\binom{m + k - 1}{k}$$$?