제 4회

제 4회는 1992년 7월 12일부터 21일까지 독일 본에서 열렸다. 문제에 아직 메인 메뉴 같은 사용자 인터페이스를 요구하는 부분이 있고 입출력 체계가 문제마다 제멋대로이지만, 난이도도 많이 높아지고 제법 요즘 올림피아드 문제 같은 냄새가 나기 시작했다. 문제마다 심사 기준(배점)이 독특하고도 자세하게 적혀 있으며, '서론-문제-제한-예제-예제 파일-배점'의 형식으로 구성되어 있다.

우리 나라는 이 대회부터 참가하기 시작했다.

원문이 있는 곳: http://olympiads.win.tue.nl/ioi/ioi92/tasks92.txt

1. 미지의 대륙

2. 미로 처리

3. 바다 한가운데의 섬

4. 해밀턴의 로봇

5. 등산가 모임

6. 루빅 큐브 다루기


1. 미지의 대륙

가로 48개, 세로 16개의 정사각형 격자로 된 직사각형 모양 지도가 있다. 두 좌표가 남북 또는 동서로 이웃해 있다면 우리는 그 좌표가 서로 연결됐다고 정의하겠다. 처음에는 지도에 있는 모든 좌표가 물 아니면 육지라고만 알고 있다. 그런데 다음을 잘 읽어보자.

지도 각 칸의 속성을 다시 매기는데는 지리학상의 일정한 규칙이 있다.

어떤 위치가 위와 같은 조건에 해당하여 속성이 바뀌었다고 해도 나중에 다시 그 속성이 맞는지 그 위치를 확인해 볼 필요가 있다. 처리하는 과정에서 이웃하는 칸의 속성이 바뀌었을 수도 있기 때문이다. 더 이상 바뀔 것이 없이 모든 위치의 속성이 완전히 표기됐다면 그 지도는 조사가 끝났다고 규정한다.

문제

다음의 작업을 순서대로 하는 프로그램을 작성하라.

  1. 미지의 대륙 지도를 아스키 형식의 입력 파일에서 읽어들인 뒤 화면에 지도 모습을 초기 통계와 함께 보여준다. 초기 통계는 땅과 물의 칸수를 나타낸 것으로, 예제 1의 화면처럼 만들면 된다.
  2. 지도를 조사하여 땅과 물로만 된 정보를 앞에서 말한 지리학 규칙대로 M, P, C, O, B, L과 같이 자세하게 다시 표기한다.
  3. 조사가 끝난 지도를 최종 통계와 함께 화면에 출력한다. 최종 통계는 예제 2의 화면처럼 만들면 된다.
  4. 지도 조사와 그것의 최종 통계 결과를 아스키 파일로 저장한다.

제한

  1. 답안 프로그램을 C:\IOI\DAY-1\411-PROG.xxx라는 텍스트 파일로 저장한다. 확장자 xxx란 언어가 베이직인 경우 BAS, C언어인 경우 C, 파스칼인 경우 PAS, 로고인 경우 LCN이다.
  2. 지도 내용을 담고 있는 입력 파일은 C:\IOI\DAY-1\411-MAP.IN이어야 한다.
  3. 출력 파일은 C:\IOI\DAY-1\411-MAP.OU여야 한다.

예제

예제 1: 미지의 대륙 지도를 담고 있는 C:\IOI\DAY-1\411-MAP.IN 파일을 초기 통계와 함께 출력한 모습은 아래와 같아야 한다.

WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWGGGGGGWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWGGWWGGWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWGGGWGGWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWGGWWGGWWWGGGWGWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWGGGGGGGGGGGGGWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWGGGWWWGGWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWGGGWWWGGWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWGGGGWWGGWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWGGWWWGGWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWGWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWGWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWGGGWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
미지의 대륙: G=61 W=707 ALL=768

예제 2: 위의 지도를 조사하여 그것의 최종 통계를 저장한 C:\IOI\DAY-1\411-MAP.OU의 내용은 아래와 같아야 한다.

OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOCCCCCCOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOCCLLCCOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOCMPLCCOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOCCLLCCBBBCCCBPOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOBCCCCCCCCMCCCCBOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOBCMCBBBCCOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOCMCBOOCCOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOCMMPOOCCOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOBCCBOOCCOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOBPBOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOBPBOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOPPPOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
조사가 끝남: P=8 C=47 M=6 O=685 B=17 L=5 ALL=768

예제 파일

응시자의 편의를 위해 위의 예제 파일을 C:\IOI\DAY-1\411-MAP.IN과 C:\IOI\DAY-1\411-MAP.OU로 만들어 두었다.

주의: 답안 프로그램이 예제 파일에서 바른 답을 출력했다고 프로그램이 반드시 올바르게 만들어진 것은 아니다.

배점 (최고 100점)


2. 미로 처리

M×N 평면을 완전히 차지하고 있는 미로가 있다. 미로는 통과할 수 없는 벽을 나타내는 칸과 통과할 수 있는 공백을 나타내는 칸이 여러 개 모여 구성된다. 공백에는 입구도 있고, 우리의 목적지인 보물도 포함되어 있다.

여러 공백이 입구부터 막다른 끝(끝점)까지 한 방향으로 인접하여 연결된 것을 길이라고 부른다. 길 주위는 벽으로 둘러싸여 있다. 길의 길이는 입구와 끝점을 포함하여 공백인 칸의 개수이다.

미로는 이러한 길로 이루어지며, 입구부터 시작해 길을 따라가 보면, 길이 여러 갈래로 갈라지는 경우는 있으나 길이 합쳐지는 경우는 없다. 그래서 두 행로가 한 점에 만나서 끝나지 않는다. 입구는 미로 가장 위쪽 어딘가에 있다. 보물은 입구에서 가장 멀리 떨어진 길의 끝점에 있다.

M×N 크기의 미로에는 최대한 많은 길이 있어야 한다. 즉 어디든 더 이상 길을 내면 위 조건을 만족하게 될 수 없게 될 정도가 되어야 한다.

미로가 계산되며 평면 위에 계속 생겨나는 모습을 지켜보는 건 재미있다. 하지만 알고리즘 자체는 아주 빨리 실행되기 때문에 칸이 하나 그려지고 나서 지연 시간을 두는 게 필요하다.

문제

다음과 같이 미로와 관련된 작업을 하는 유틸리티 프로그램을 작성하라. 다음 기능은 메인 메뉴를 통해 아무 순서대로 몇 번이고 실행될 수 있어야 한다.

제한

1. 미로의 칸은 다음 두 글자로 표현한다.

2. M과 N은 3 이상 20 이하여야 한다.

3. 답안 프로그램을 C:\IOI\DAY-1\412-PROG.xxx라는 텍스트 파일로 저장한다. 확장자 xxx란 언어가 베이직인 경우 BAS, C언어인 경우 C, 파스칼인 경우 PAS, 로고인 경우 LCN이다.

4. 읽고 쓸 아스키 파일은 C:\IOI\DAY-1\412-MAZE.IO여야 한다.

답안 프로그램을 실행한 예

예제 1: 예제 파일인 C:\IOI\DAY-1\412-MAZ1.IO를 읽어 5번 기능을 이용하여 화면에 표시하였다.

M = 10, N = 8, DELAY TIME = 100 
■■■■■■. ■■■
■■■    . . ■  ■
■■    ■. ■    ■
■    ■  . . ■  ■
■  ■    ■. .   ■
■■    ■  ■. ■■
■    ■T . . .   ■
■■■■■■■■■■
LENGTH = 13 

예제 2: 같은 예제 파일을 4번 기능으로 출력한 모습이다.

10   8
■■■■■■  ■■■
■■■        ■  ■
■■    ■  ■    ■
■    ■      ■  ■
■  ■    ■      ■
■■    ■  ■  ■■
■    ■T         ■
■■■■■■■■■■

예제 파일

응시자의 편의를 위해 위의 예제 파일을 C:\IOI\DAY-1\412-MAZ1.IO와  C:\IOI\DAY-1\412-MAZ2.IO란 이름으로 만들어 두었다.

주의: 답안 프로그램이 예제 파일에서 바른 답을 출력했다고 프로그램이 반드시 올바르게 만들어진 것은 아니다.

배점 (최고 100점)


3. 바다 한가운데의 섬

바다는 N×N크기의 격자로 표현된다. 격자에 있는 "*" 표시는 바다에 있는 섬을 뜻한다. 이번 문제는 격자에 있는 섬의 가로와 세로 분포를 기호화해 놓은 정보만으로 바다 지도를 재현하는 것이다. 기호화 규칙에 대한 이해를 돕기 위해 다음 지도를 보자.

*   * *       1 2 
  * * *   *   3 1 
*   *   *     1 1 1 
  * * * * *   5 
* *   *   *   2 1 1 
      *       1 
1 1 4 2 2 1 
1 2   3   2 
1 

오른쪽에 있는 숫자들은 각 줄에 있는 섬 집단의 순서와 크기를 나타낸다. 예를 들어 첫째 줄 "1 2"는 앞에 섬 하나가 있고 다음에 이어진 섬 두 개가 있다는 뜻이다. 섬 사이나 섬 좌우 끝에 있는 바다의 길이는 얼마가 되든 상관없다. 마찬가지로 첫째 칸에 있는 "1 1 1" 역시 따로 떨어진 한 개 짜리 섬 집단이 세 개가 있다는 것을 뜻한다.

문제

한 입력 파일에는 여러 지도 정보들이 있다. 이들을 모두 읽을 때까지 다음 처리를 되풀이하는 프로그램을 작성하라.

  1. 같은 입력 파일에서 한 지도 정보를 읽는다. (입력 파일의 구조는 예제 파일 내용에 나타나 있으므로 참고하라.) 그리고 그것을 화면에 출력한다. 지도 정보는 처음에 정사각형 격자 크기가 나오고, 다음에 줄의 정보, 칸의 정보가 순서대로 들어있다. 한 행 또는 한 열의 정보를 나타내는 수열은 한 줄에 실려 있으며 0으로 끝난다. 수치 사이에는 공백이 있다.
  2. 정보를 바탕으로 지도를 재구성하여 화면에 출력한다. 답이 둘 이상 있으면 모두 찾아 출력한다.
  3. 만들어진 지도를 출력 파일에 저장한다. 바다 한 칸은 공백 두 칸으로 표현한다. 섬 역시 "* "로, 뒤에 공백이 붙는다. 한 조건을 만족하는 답이 여러 개 있으면 답 사이를 빈줄로 구분한다. 또한, 답이 없으면 "답이 없음"이라고 출력한다. 그리고 한 정보에 대한 답을 다 구하고 다음 정보를 읽을 때는 출력 파일에도 "다음 문제"라는 문장을 넣어 답을 서로 구분한다.

제한

  1. N은 1 이상 8 이하이다.
  2. 답안 프로그램을 C:\IOI\DAY-1\413-PROG.xxx라는 텍스트 파일로 저장한다. 확장자 xxx란 언어가 베이직인 경우 BAS, C언어인 경우 C, 파스칼인 경우 PAS, 로고인 경우 LCN이다.
  3. 입력 파일은 C:\IOI\DAY-1\413-SEAS.IN이어야 한다.
  4. 출력 파일은 C:\IOI\DAY-1\413-SEAS.OU여야 한다.

예제

6        ← 예제 1: (위의 예제 그림): 6은 격자의 크기이다.
1 2 0    ← 첫째 줄의 정보
3 1 0 
1 1 1 0 
5 0 
2 1 1 0 
1 0 
1 1 1 0  ← 첫째 칸의 정보
1 2 0 
4 0 
2 3 0 
2 0 
1 2 0 
 
4     ← 예제 2: 답은 아래와 같다.
0            1 2 3 4
1 0        1        
2 0        2     *  
0          3   * *
0          4
1 0
2 0 
0 
 
2     ← 예제 3: 이 조건을 만족하는 해는 없다.
0
0 
2 0 
2 0 
 
2     ← 예제 4: 이 조건을 만족하는 해가 두 개 있다.
1 0
1 0
1 0
1 0

예제 파일

응시자의 편의를 위해 위의 예제 파일을 C:\IOI\DAY-1\413-SEAS.IN와  C:\IOI\DAY-1\413-SEAS.OU란 이름으로 만들어 두었다.

주의: 답안 프로그램이 예제 파일에서 바른 답을 출력했다고 프로그램이 반드시 올바르게 만들어진 것은 아니다.

배점 (최고 100점)


4. 해밀턴의 로봇

평면 위에 P1, P2, ..., PN까지 N개의 점이 있다. 이들의 위치는 (X1, Y1), (X2, Y2), ..., (XN, YN)이다.

로봇은 P1부터 시작해 이 점들을 통해 움직여야 한다. 또한 한 번 지난 점을 다시 지날 수 없으며, 모든 점을 한 번만 통과한 뒤 마지막에 P1 위치로 되돌아와야 한다.

로봇은 일정한 규칙대로만 움직일 수 있다. 우선 점을 향해 직선 방향으로만 움직일 수 있다. 처음 P1점에서 움직이기 시작할 때는 방향을 어느 쪽으로든 잡을 수 있다. 그러나 Pi점에 닿고 나서부터는 좌우 90도 단위로 방향을 튼 곳으로만 움직일 수 있다.

로봇을 조종하는 프로그램은 다음 다섯 가지의 구문으로 되어 있다.

문제

다음과 같은 작업을 하는 프로그램을 작성하라.

  1. 아스키 파일에서 N의 값을 읽고, N개의 좌표도 읽어들인다. (예제를 참조할 것) 그리고 자료들을 화면에 출력한다.
  2. 로봇이 제한 조건을 만족하며 모든 점을 한 번씩 순회하게 하는 로봇 조종 프로그램을 작성한다. 조종 프로그램의 문법은 위를 참조하라.
  3. 그런 행로가 없으면 로봇 프로그램 코드에는 "STOP"문 하나만 있어야 한다.
  4. 모든 점을 순회하는 행로가 있는지 여부를 화면에 출력하고, 있으면 행로 총 길이를 반올림하여 소수 둘째 자리까지 표시한다. 행로 총 길이는 거쳐 간 각 점까지의 직선 거리의 합이다.
  5. 로봇 조종 프로그램 코드를 예제처럼 아스키 파일로 저장한다.

제한

  1. 답안 프로그램을 C:\IOI\DAY-1\421-PROG.xxx라는 텍스트 파일로 저장한다. 확장자 xxx란 언어가 베이직인 경우 BAS, C언어인 경우 C, 파스칼인 경우 PAS, 로고인 경우 LCN이다.
  2. 읽어들이는 파일 이름은 C:\IOI\DAY-2\421-ROBO.IN이다.
  3. 로봇 조종 프로그램은 C:\IOI\DAY-2\421-ROBO.OU로 저장한다.
  4. 입력된 값이 N의 값이 4보다 작거나 16보다 크면 프로그램은 입력을 받아들이지 말아야 한다.

예제

입력: 입력 파일의 첫 줄에는 N의 값이 있고, 다음 N줄에는 평면 위 점의 X, Y좌표가 아래의 예처럼 들어있다.

4 
2 -2 
0 2 
-1 -1 
3 1 

출력: 위의 점 4개를 조건을 만족하며 갈 수 있는 가장 짧은 행로 길이는 12.65이다.

ORIENTATION 3 1
MOVE-TO 3 1
TURN-LEFT
MOVE-TO 0 2
TURN-LEFT
MOVE-TO -1 -1
TURN-LEFT
MOVE-TO 2 -2
STOP

예제 파일

응시자의 편의를 위해 위의 예제 입출력 파일을 C:\IOI\DAY-2\421-ROBO.IN과  C:\IOI\DAY-2\421-ROBO.OU로 만들어 두었다.

주의: 답안 프로그램이 예제 파일에서 바른 답을 출력했다고 프로그램이 반드시 올바르게 만들어진 것은 아니다.

배점 (최고 100점)


5. 등산가 모임

어떤 등산가 모임에는 1부터 P까지 번호가 매겨진 P명의 회원이 있다. 모든 회원들은 같은 속도로 산을 오른다. 올라갈 때와 내려갈 때의 속도차는 없다. 번호가 i인 회원은 최대 S(i)만큼 지원 물자(식량, 소모품 등)를 질 수 있고, 등산 또는 하산하면서 하루에 C(i)만큼의 물자를 소비한다. C(i)와 S(i)의 값은 모두 정수이다.

충분한 지원 물자를 갖춘 한 등산가가 산꼭대기에 오르기 위해서 N일이 걸린다고 가정하자. 다만 산은 너무 높아서 한 사람만으로는 오르는 데 필요한 지원 물자를 다 못 나를 수도 있다. 그래서 등산가들이 단체로 같은 장소, 같은 시각에 산을 오른다. 어떤 등산가는 꼭대기에 도달하기 전에, 남은 자기 물자 중 불필요하여 남는 양을 다른 등산가에게 주고 산을 내려온다. 여행 중 등산가들이 쉬는 일은 없다. 다시 말하지만 등산가는 산을 내려갈 때도 올라갈 때와 똑같은 양의 물자가 필요하다.

문제는 등산가 클럽의 등산 계획을 짜는 것이다. 등산가 중 적어도 한 명은 산꼭대기까지 올라야 하며 산을 올라갔던 회원들은 도중 물자가 바닥나는 일없이 무사히 하산할 수 있어야 한다.

문제

다음과 같은 작업을 하는 프로그램을 작성하라.

1. 산에 오르는 데 걸리는 날 수 N, 클럽의 회원 수 P의 값을 키보드로 입력받고, 다음 1부터 P까지 S[i]와 C[i]의 값도 차례로 입력받는다. 모두 정수만 입력받는다고 가정해도 좋다. 엉뚱한 값이 들어오면 그 입력을 받아들이지 않는다.

2. 등산 스케줄을 짠다. 회원 중 등산에 참여할 사람을 정하고, 이 사람이 등산을 시작할 때 지고 갈 물자의 양도 각각 정한다. N, S(i), C(i)의 값에 따라서는 스케줄을 짜는 게 불가능한 경우도 있을 수 있다.

3. 화면에 다음 정보를 출력한다.

4. 등산에 참여하는 회원이 적고 쓰이는 물자(회원들이 등산할 때 쓰려고 갖고 가는 물자의 합)가 적을수록 스케줄이 최적으로 잡혔다고 말한다. 조건을 만족하는 최적의 스케줄을 찾아보기 바란다.

제한

  1. 답안 프로그램을 C:\IOI\DAY-1\422-PROG.xxx라는 텍스트 파일로 저장한다. 확장자 xxx란 언어가 베이직인 경우 BAS, C언어인 경우 C, 파스칼인 경우 PAS, 로고인 경우 LCN이다.
  2. 답안 프로그램은 N이 1 미만이거나 100을 초과하는 경우, 또 P가 1 미만이거나 20을 초과하는 입력이 들어온 경우 입력을 받아들이지 말아야 한다.

답안 프로그램의 실행예

다음은 답안 프로그램을 사용한 결과의 일례이다.

산을 오르는 데 걸리는 날수:  4 
클럽 회원 수: 5 
등산가 1의 최대 물자 적재량: 7
등산가 1의 하루 소비 물자량: 1
등산가 2의 최대 물자 적재량: 8
등산가 2의 하루 소비 물자량: 2
등산가 3의 최대 물자 적재량: 12
등산가 3의 하루 소비 물자량: 2
등산가 4의 최대 물자 적재량: 15
등산가 4의 하루 소비 물자량: 3
등산가 5의 최대 물자 적재량: 7
등산가 5의 하루 소비 물자량: 1
 
필요한 등산가: 2명,  필요한 총 물자량: 10. 
산을 오르는 등산가 번호: 1, 5
등산가 1이(가) 물자를 7만큼 지고 등산하여 4일 뒤 하산합니다.
등산가 5이(가) 물자를 3만큼 지고 등산하여 1일 뒤 하산합니다.
다른 클럽의 등산 스케줄을 작성하겠습니까? (Y/N) Y 
 
산을 오르는 데 걸리는 날수: 2
클럽 회원 수: 1
등산가 1의 최대 물자 적재량: 3
등산가 1의 하루 소비 물자량: 1
등산 스케줄을 짤 수 없습니다.
다른 클럽의 등산 스케줄을 작성하겠습니까? (Y/N) N
 
고맙습니다.

예제 파일

응시자의 편의를 위해 테스트해 볼 자료와 그것의 올바른 출력 예제를 파일로 만들어 두었다. C:\IOI\DAY-2 디렉토리를 살펴보기 바란다.

주의: 답안 프로그램이 예제 파일에서 바른 답을 출력했다고 프로그램이 반드시 올바르게 만들어진 것은 아니다.

배점 (최고 100점)


6. 루빅 큐브 다루기

이번 문제는 퍼즐 게임인 "루빅 큐브"와 관련된 것이다.

루빅 큐브에 대해 아는 바가 있는 사람은 이 부분을 읽지 않아도 될 것이다. 루빅 큐브란 3×3×3개의 작은 정육면체로 이루어진 큰 정육면체를 말한다. 이것의 여섯 면은 서로 모두 다른 색으로 칠해져 있다. 이를 초기 상태라고 부르겠다. 루빅 큐브의 각각의 면 여섯 개는 3×3 크기의 작은 정육면체의 면으로 이루어져 있음을 알 수 있다.

여러분이 루빅 큐브의 여섯 면 중 아무 면이나 보고 있다고 상상해 보자. 작은 3×3의 정육면체로 이루어진 여섯 겉면은 그 면 가운데를 직교하는 축을 기준으로 하여 90도의 배수 각도로 회전시킬 수 있다. 그러면 그 면과 만나는 네 면에 있는 작은 정육면체의 한 열의 색도 바뀌고 자연적으로 옆 네 면의 색깔 형태도 바뀌게 된다.

이번 문제에서는 루빅 큐브의 각 면을 색깔 대신 이름으로 구분한다. U(위), R(오른쪽), F(앞), B(뒤), L(왼쪽), D(아래)이다. 순서대로 돌리는 면을 나열한 것을 동작열이라 하여 문자 {U, R, F, B, L, D}로 기술한다. 각 문자는 루빅 큐브의 그 면을 시계 방향으로 90도 돌린 것을 의미한다.

문제와 예제

사용자가 다음 세 문제를 어떤 순서로든 풀 수 있게 하는 프로그램을 작성하라. 입력받는 문자열의 최대 길이는 35자라고 가정한다.

1. 어떤 면을 90도 회전할지 동작을 순서대로 나열한 목록(이하 동작열)을 입력받아 실질적으로 이와 같은 회전 결과를 만드는 데 필요한 가장 짧은 동작열을 구하라. 즉 같은 방향으로 회전한 것이 세 번을 넘게 나오게 하지 않는다는 뜻이다. 이해를 돕기 위해 예를 들었다.

L → L        LL  → LL       LLL → LLL
LLLL → 원래 상태     LLLLL → L      LLRRRFFFFRLB → LLLB
HELLO → 에러

2. 초기 상태에 있는 두 루빅 큐브를 각각 다음 동작열대로 회전시키면 두 방법 모두 같은 결과가 나오는지 판별하라. 역시  예를 들어보았다.

RL, LR → 예
RU, UR → 아니오
RRFFRRFFRRFFRRFF, FFRRFFRR → 예
RRFFRRFFRRFFRRFF, RRFFRRFF → 아니오

3. 초기 상태에 있는 루빅 큐브를 지정된 동작열대로 회전시키는 것을 최소 몇 번 반복하면 도로 초기 상태로 돌아가는가를 계산하라. 이를 계산한 예는 다음과 같다.

L → 4        DD → 2     BLUB → 36
RUF → 80     BLUFF → 180 

제한

  1. 답안 프로그램을 C:\IOI\DAY-1\423-PROG.xxx라는 텍스트 파일로 저장한다. 확장자 xxx란 언어가 베이직인 경우 BAS, C언어인 경우 C, 파스칼인 경우 PAS, 로고인 경우 LCN이다.

예제 파일

예제 파일은 없다.

배점 (최고 100점)