Problem D
Die Hard
John and Hans are playing a game involving 3 dice. Even though they are all 6-sided, they are not guaranteed to be identical.
First John picks one of the dice and then Hans picks one of the remaining two. Then they both roll their chosen die. If they roll the same number, they both re-roll their die. Otherwise the winner is the one who rolled the highest number.
In case neither John or Hans can win with their chosen dice, they do not bother to re-roll the dice indefinitely and no winner is declared.
Can you help John pick a die that guarantees that he wins with a probability of at least $\frac{1}{2}$?
Input
The input consists of three lines. Line $i$ contains $6$ positive integers $x_ j$ ($1 \leq x_ j \leq 1000$), describing the sides of the $i$’th die.
Output
Output the smallest $i \in \{ 1, 2, 3\} $, such that John can pick die $i$ and be guaranteed to win with probability at least $\frac{1}{2}$. If no such die exists, output “No dice”.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 2 4 4 9 9 1 1 6 6 8 8 7 7 5 5 3 3 |
No dice |
| Sample Input 4 | Sample Output 4 |
|---|---|
1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 |
No dice |
