Informatica Online Judge

  The Clocks (시계, IOI-94) [0263 / 0107]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 85   Total Tried : 89


The Champion of this Problem (C++) : gs18117 - ms / 705byte
My Best Submission (C++) : N/A

[]

Background

아래 그림과 같이 3*3으로 9개의 시계가 있다고 가정하자.



이 문제의 목적은 이 9개의 시계를 모두 12시로 맞추는 것이다. (주어진 모든 시계의 초기상태는 3, 6, 9, 12시의 4가지만 존재한다.)

시계에 적용할 수 있는 연산은 아래와 같은 9가지가 있으며 각 연산이 적용된 시계들의 바늘은 모두 시계방향으로 90도 회전한다.

방법 1 : A B D E 시계
방법 2 : A B C 시계
방법 3 : B C E F 시계
방법 4 : A D G 시계
방법 5 : B D E F H 시계
방법 6 : C F I 시계
방법 7 : D E G H 시계
방법 8 : G H I 시계
방법 9 : E F H I 시계

위 방법들을 활용하여 최소의 연산으로 시계를 모두 12시로 만드는 연산 순열을 출력하는 프로그램을 작성하시오.

Input

한 줄에 3개씩 세 줄에 걸쳐서 A, B, C, ... , I까지의 시계의 시각이 주어진다.

Output

모든 시계를 12시로 만드는 최소 연산 순열을 한 줄로 출력한다. 단 한 가지 이상의 방법이 존재할 경우에는 순열의 각 값을 연결했을 때 값이 더 적은 것을 출력한다.
EX) 5 2 4 6과 9 3 1 1의 2가지가 가능했다면 5426 < 9311이므로 5 2 4 6을 출력한다.

IO Example

입력
9 9 12
6 6 6
6 3 6

출력
4 5 8 9

설명)
9 9 12
6 6 6
6 3 6

4를 적용

12 9 12
9 6 6
9 3 6

5를 적용

12 12 12
12 9 9
9 6 6

8을 적용
12 12 12
12 9 9
12 9 9

9를 적용
12 12 12
12 12 12
12 12 12

가 된다.

IOI(International Olympiad in Informatics) - 1994

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]