동전

면접 대비

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

요약

12개 동전 중 저울 세 번의 결과를 보고 위조 동전과 그것이 무겁거나 가벼운지를 찾거나 impossible/indefinite를 판정합니다.

문제

양팔 저울 하나와 1번부터 12번까지 번호가 매겨진 동전 12개가 있습니다. 이 중 정확히 한 개가 모조품이며, 모조품은 나머지 진짜 동전보다 무겁거나 가볍습니다. 진짜 동전은 모두 무게가 같습니다.

양팔 저울로 세 번 측정한 결과가 주어질 때, 모조품이 몇 번 동전인지, 그리고 진짜 동전보다 무거운지 가벼운지 알아내는 프로그램을 작성하세요.

입력은 세 줄로 이루어지며, 각 줄은 한 번의 측정 결과를 다음 형식으로 나타냅니다.

A B C D x E F G H

A, B, C, D, E, F, G, H는 서로 다른 8개 동전의 번호이고, x는 <, >, = 중 하나로 다음을 의미합니다.

모조품을 유일하게 알아낼 수 있으면, 모조품의 번호를 출력하고 그 뒤에 진짜 동전보다 무거우면 +, 가벼우면 -를 이어서 출력합니다. (예: 2+)

세 번의 측정 결과가 서로 모순되어 어떤 동전도 조건을 만족할 수 없으면 impossible을 출력합니다.

측정 결과가 모순되지는 않지만, 모조품의 번호나 그것이 무거운지 가벼운지를 유일하게 결정할 수 없으면 indefinite를 출력합니다.

예제 1

입력

1 2 3 10 > 4 5 6 11
1 2 3 11 > 7 8 9 10
1 4 7 10 < 2 5 8 12

예상 출력

2+

예제 2

입력

1 4 6 10 < 5 7 9 12
2 5 4 11 > 6 8 7 10
3 6 5 12 < 4 9 8 11

예상 출력

6-

예제 3

입력

1 2 3 4 < 5 6 7 8
5 6 7 8 < 9 10 11 12
9 10 11 12 < 1 2 3 4

예상 출력

impossible

예제 4

입력

4 8 10 11 = 1 2 5 7
2 4 7 12 = 8 9 10 11
3 7 10 11 > 6 8 9 12

예상 출력

indefinite