제 4회는 1992년 7월 12일부터 21일까지 독일 본에서 열렸다. 문제에 아직 메인 메뉴 같은 사용자 인터페이스를 요구하는 부분이 있고 입출력 체계가 문제마다 제멋대로이지만, 난이도도 많이 높아지고 제법 요즘 올림피아드 문제 같은 냄새가 나기 시작했다. 문제마다 심사 기준(배점)이 독특하고도 자세하게 적혀 있으며, '서론-문제-제한-예제-예제 파일-배점'의 형식으로 구성되어 있다.
우리 나라는 이 대회부터 참가하기 시작했다.
원문이 있는 곳: http://olympiads.win.tue.nl/ioi/ioi92/tasks92.txt
가로 48개, 세로 16개의 정사각형 격자로 된 직사각형 모양 지도가 있다. 두 좌표가 남북 또는 동서로 이웃해 있다면 우리는 그 좌표가 서로 연결됐다고 정의하겠다. 처음에는 지도에 있는 모든 좌표가 물 아니면 육지라고만 알고 있다. 그런데 다음을 잘 읽어보자.
지도 각 칸의 속성을 다시 매기는데는 지리학상의 일정한 규칙이 있다.
어떤 위치가 위와 같은 조건에 해당하여 속성이 바뀌었다고 해도 나중에 다시 그 속성이 맞는지 그 위치를 확인해 볼 필요가 있다. 처리하는 과정에서 이웃하는 칸의 속성이 바뀌었을 수도 있기 때문이다. 더 이상 바뀔 것이 없이 모든 위치의 속성이 완전히 표기됐다면 그 지도는 조사가 끝났다고 규정한다.
다음의 작업을 순서대로 하는 프로그램을 작성하라.
예제 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로 만들어 두었다.
주의: 답안 프로그램이 예제 파일에서 바른 답을 출력했다고 프로그램이 반드시 올바르게 만들어진 것은 아니다.
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란 이름으로 만들어 두었다.
주의: 답안 프로그램이 예제 파일에서 바른 답을 출력했다고 프로그램이 반드시 올바르게 만들어진 것은 아니다.
바다는 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" 역시 따로 떨어진 한 개 짜리 섬 집단이 세 개가 있다는 것을 뜻한다.
한 입력 파일에는 여러 지도 정보들이 있다. 이들을 모두 읽을 때까지 다음 처리를 되풀이하는 프로그램을 작성하라.
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란 이름으로 만들어 두었다.
주의: 답안 프로그램이 예제 파일에서 바른 답을 출력했다고 프로그램이 반드시 올바르게 만들어진 것은 아니다.
평면 위에 P1, P2, ..., PN까지 N개의 점이 있다. 이들의 위치는 (X1, Y1), (X2, Y2), ..., (XN, YN)이다.
로봇은 P1부터 시작해 이 점들을 통해 움직여야 한다. 또한 한 번 지난 점을 다시 지날 수 없으며, 모든 점을 한 번만 통과한 뒤 마지막에 P1 위치로 되돌아와야 한다.
로봇은 일정한 규칙대로만 움직일 수 있다. 우선 점을 향해 직선 방향으로만 움직일 수 있다. 처음 P1점에서 움직이기 시작할 때는 방향을 어느 쪽으로든 잡을 수 있다. 그러나 Pi점에 닿고 나서부터는 좌우 90도 단위로 방향을 튼 곳으로만 움직일 수 있다.
로봇을 조종하는 프로그램은 다음 다섯 가지의 구문으로 되어 있다.
다음과 같은 작업을 하는 프로그램을 작성하라.
입력: 입력 파일의 첫 줄에는 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로 만들어 두었다.
주의: 답안 프로그램이 예제 파일에서 바른 답을 출력했다고 프로그램이 반드시 올바르게 만들어진 것은 아니다.
어떤 등산가 모임에는 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. 등산에 참여하는 회원이 적고 쓰이는 물자(회원들이 등산할 때 쓰려고 갖고 가는 물자의 합)가 적을수록 스케줄이 최적으로 잡혔다고 말한다. 조건을 만족하는 최적의 스케줄을 찾아보기 바란다.
다음은 답안 프로그램을 사용한 결과의 일례이다.
산을 오르는 데 걸리는 날수: 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 디렉토리를 살펴보기 바란다.
주의: 답안 프로그램이 예제 파일에서 바른 답을 출력했다고 프로그램이 반드시 올바르게 만들어진 것은 아니다.
이번 문제는 퍼즐 게임인 "루빅 큐브"와 관련된 것이다.
루빅 큐브에 대해 아는 바가 있는 사람은 이 부분을 읽지 않아도 될 것이다. 루빅 큐브란 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
예제 파일은 없다.