Alice and Bob are discussing penalty shoot-outs and their randomness: "We might as well be throwing dice to determine the winner!", Alice said. And so they started simulating penalty shoot-outs by each throwing dice, summing the points indicated on their dice, and comparing these sums. The player with the largest sum wins; in case both sums are equal, there is a tie.
But even in such situations, some player might have an edge over their opponent, depending on which dice they throw. Thus, just by looking at the dice they are about to throw, Alice and Bob want to determine who has the better edge.
Alice has $$$M$$$ fair dice, with $$$A_1, A_2, \dots, A_M$$$ sides. For all integers $$$k$$$ and $$$l$$$ such that $$$1 \leq k \leq M$$$ and $$$1 \leq l \leq A_k$$$, the $$$k^\text{th}$$$ die of Alice has a probability $$$1/A_k$$$ of showing its face numbered $$$l$$$. Then, Alice's score is the sum of the numbers displayed by her $$$M$$$ dice. Similarly, Bob has $$$N$$$ fair dice, with $$$B_1, B_2, \dots, B_N$$$ sides.
Given these dice, Alice has a probability $$$\mathbb{P}_A$$$ of having a strictly larger score than Bob, and Bob has a probability $$$\mathbb{P}_B$$$ of having a strictly larger score than Alice. Which probability is the largest one?
The input consists of three lines, each one containing space-separated integers. The first line contains the numbers $$$M$$$ and $$$N$$$. The second line contains the numbers $$$A_1, A_2, \dots, A_M$$$. The third line contains the numbers $$$B_1, B_2, \dots, B_N$$$.
Limits
The output should contain a single line, consisting of a single uppercase word: ALICE if $$$\mathbb{P}_A > \mathbb{P}_B$$$, TIED if $$$\mathbb{P}_A = \mathbb{P}_B$$$, and BOB if $$$\mathbb{P}_A < \mathbb{P}_B$$$.
8 1 4 4 4 4 4 4 4 4 6
ALICE
2 2 6 4 4 6
TIED
Sample Explanation 1
Since Alice has 8 dice, her score is always 8 or more; Bob's score is always 6 or less. Hence, Alice has a probability $$$\mathbb{P}_A = 100\%$$$ of beating Bob, and he has a probability $$$\mathbb{P}_B = 0\%$$$ of beating her. Consequently, $$$\mathbb{P}_A > \mathbb{P}_B$$$.
Sample Explanation 2
Alice has a probability $$$\mathbb{P}_A = 125/288$$$ of beating Bob; he also has a probability $$$\mathbb{P}_B = 125/288$$$ of beating her.
Name |
---|