Die Hard

면접 대비

시간 제한1초메모리 제한1024 MB

요약
눈금이 중복될 수 있는 6면체 주사위 3개가 주어질 때, 존이 먼저 하나를 고르고 한스가 남은 둘 중 하나를 고르면, 어느 쪽을 골라도 존이 이길 확률이 1/2 이상이 되는 가장 작은 주사위 번호를 찾는다.
난이도

보통10점 중 4점

유형
확률, 완전 탐색, 구현, 수학
정답자
아직 제출이 없습니다

문제

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 12\frac{1}{2}?

입력

The input consists of three lines. Line ii contains 66 positive integers x_jx\_j (1≤x_j≤10001 \leq x\_j \leq 1000), describing the sides of the ii'th die.

출력

Output the smallest i∈1,2,3i \in \\{1, 2, 3\\}, such that John can pick die ii and be guaranteed to win with probability at least 12\frac{1}{2}. If no such die exists, output "No dice".

예제4

  1. 예제 1

    입력
    1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
    예상 출력
    1

  2. 예제 2

    입력
    1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 3 3 3
    예상 출력
    3

  3. 예제 3

    입력
    2 2 4 4 9 9
1 1 6 6 8 8
7 7 5 5 3 3
    예상 출력
    No dice

  4. 예제 4

    입력
    1 1 1 1 1 1
2 2 2 2 2 2
2 2 2 2 2 2
    예상 출력
    No dice