제 2회는 1990년 7월 15일부터 21일까지 소련 백러시아 민스크에서 열렸다. 문제가 가장 많이 출제됐던 이 대회에는 게임을 포함해서 다양한 소재의 문제가 출제되었지만 아직 입출력 형태는 요즘의 형식과 많은 차이가 있었다. 그렇지만 문제가 그리 만만하게 풀리지는 않을 것이다. 한편, 5번 문제에는 지정된 언어로 프로그램을 짜라는 지시까지 있어 정말 특이하다.
원문이 있는 곳: http://olympiads.win.tue.nl/ioi/ioi90/tasks90.txt
표 A에 있는 숫자들을 표 B로 재배열하는 과정을 프로그램 하라. 재배열 동작은 일반적인 숫자 퍼즐을 풀 듯이 공백이 있는 칸과 그것의 좌우 상하에 있는 한 숫자 칸을 맞바꾸는 것을 되풀이하는 것이다.
+----+----+----+----+ +----+----+----+----+
| 7 | 3 | 5 | 14 | | 1 | 2 | 3 | 4 |
+----+----+----+----+ +----+----+----+----+
| | 4 | 9 | 13 | | 5 | 6 | 7 | 8 |
+----+----+----+----+ --------> +----+----+----+----+
| 1 | | 2 | 10 | | 9 | 10 | 11 | 12 |
+----+----+----+----+ +----+----+----+----+
| 11 | 8 | 12 | 6 | | 13 | 14 | | |
+----+----+----+----+ +----+----+----+----+
A B
박스 게임은 격자에 있는 점을 선으로 이으며 진행하는 게임이다. 선을 하나 그어 상자 모양을 완성하는 사람은 점수를 얻고 또 수를 둘 기회를 얻는다. 모든 점이 선으로 완전히 연결되어 격자가 완성되면 게임이 끝나며, 점수가 더 많은 쪽이 이기게 된다. 두 점을 사이를 이을 때는 가로줄 또는 세로줄만 이용할 수 있다.
다음은 빨간색과 파란색 선으로 게임을 하여 게임이 반쯤 완성된 모습이다.
o----o o----o----o
| | | | |
| | | | |
o----o----o----o----o
| |
| |
o o o o----o
|
|
o----o o----o o
| |
| |
o o o o----o
이 게임판의 모습을 선 종류인 R과 B, 그리고 선이 아무 것도 없음을 뜻하는 O라는 문자로 다음과 같이 표현할 수도 있다.
R O B R B R B B B B B R R R O R O O O O O B B O O O O B O R O O R O O R O O O B
그리고 이것을 마지막으로 다음과 같이 간략하게 나타내 보겠다.
ROBR BRBBB BBRR ROROO OOOB BOOOO BORO OROOR OOOB
1. 위와 같은 행렬을 읽어서(행렬은 언제나 5×5 크기의 격자 모양이다.) 변이 세 개만 있는 상자의 개수를 계산하는 프로그램을 작성하라. 상자의 열린 방향은 어느 쪽이든 상관없다. 데이터는 파일에서 읽어야 한다. 입력 파일에는 총 9r개의 줄이 있으며 r은 이제까지의 게임 횟수를 뜻한다. 파일에 위와 같은 자료가 r개 있다는 뜻이다. 그리고 파일은 마지막 줄 첫 칸에 적힌 END라는 구문으로 끝난다. 응시자의 답안 프로그램은 데이터에 있는 각 행렬에 대한 출력 결과로 다음 한 줄을 출력한다.
행렬 r에는 변이 세 개인 상자가 x개 있습니다.
2. 1번 문제를 푼 답안 프로그램을 고쳐서 프로그램이 파란색 편을 대신하여 게임을 혼자 진행하도록 하여라. 한 수 한 수마다 상자를 될 수 있으면 많이 만들 수 있게 게임을 해야 한다. 상자를 하나 완성하면 수를 또 둘 수 있다는 것을 염두에 두기 바란다. 마지막 수는 관계가 없지만, 불가피한 상황이 아니면 변이 3개 있는 상자를 만들어서는 안 된다.
자기 수를 다 두면 답안 프로그램은 다음을 출력하고 프로그램을 끝내도록 한다.
x개의 상자가 생겼습니다. 마지막 수의 위치=L, C
L과 C는 마지막 수가 놓인 게임판 위치(세로, 가로)이며, x는 답안 프로그램이 새로이 완성한 상자의 개수이다. 현재 게임판에 있는 상자의 총 수가 아님을 유의한다.
책 N권과 이 책들을 읽고 싶어하는 두 사람 A, B가 있다. 또한 음 아닌 정수A[I],B[I](1<=I<=N)가 있는데, 이는 각 사람이 번호가 I인 책을 읽는데 걸리는 시간이다. A와 B는 0째 시각에 동시에 책을 읽기 시작한다. 어느 순간이나 A와 B는 최대 한 권의 책을 읽고 있을 수 있으며, 한 책을 두 사람이 같이 볼 수는 없다.
2<=K<= N인 정수 K가 제시되며, 책들은 1부터 K까지 번호가 매겨져 있다. J-1째 책을 A, B 모두가 조금이라도 읽어보기 전에는 A, B 누구도 J째 책(2<=K<=N)을 읽을 수 없다.
이 외에 책을 읽는 순서는 이들에게 그리 중요하지 않기 때문에 책을 아무 순서로 읽게 해도 좋다.
또한 다른 사람보다 책을 먼저 읽어보는 게 가능하다. 이는 책을 읽다가 아무 시각에나 읽는걸 멈추고 다른 책을 읽다가 다시 원래 읽던 책의 그 부분부터 다시 읽어나갈 수 있다는 뜻이다. 독서를 중단한 시간 동안에는 그 사람은 다 읽지 못한 다른 책을 얼마든지 읽을 수 있다. (앞에서 말한 규칙에 걸리지 않는 책만)
다음 처리를 하는 프로그램을 작성하라.
1. 다음과 같은 형식으로 처리할 입력 자료를 받아들인다.
< N의 값 --> > < K의 값 --> > < A[1] --> > < B[1] --> > < A[2] --> > < B[2] --> > .......................... < A[N] --> > < B[N] --> >
2. A, B 모두 책들을 다 읽는데 필요한 가장 긴 시간 T를 구하라.
3. 위에서 제시한 제한 조건을 모두 만족하면서 A와 B가 T 시각에 책을 모두 다 읽을 수 있게 A와 B의 독서 스케줄을 각각 작성하라. 결과를 다음과 같은 형식으로 출력하도록 한다. 표에는 어떤 독자가(A나 B) 번호가 몇 번인 책을 어느 시간에 읽는지가 들어가 있어야 한다.
독자 A(또는 B)의 스케줄 책 번호 시작 시각 마치는 시각 ..... ..... ..... ..... ..... .....
4. 각 독자가 책을 다 읽지 않고 다른 책을 먼저 읽었던 횟수를 출력한다. 각 독자마다 이 횟수를 줄이려고 해 보아라.
정수 K가 있다. 그리고 N개의 칸으로 나누어진 종이조각이 있다.(K<=N<=40) 두 사람이 이것으로 게임을 한다. 이들은 번갈아 가며, 연속해 있는 K개의 빈칸을 고른 뒤, 그 칸에 선을 그어 그것을 지운다. 그렇게 하여 마지막 수를 두는 사람이 이긴다.
1 2 N +----+----+----+----+- -----+----+ | | | | | . . . | | +----+----+----+----+- -----+----+
1. N의 값을 입력받은 뒤 그 N에 대해 첫째 선수(게임을 먼저 하는 사람)가 반드시 이길 수 있는지 판단하라. 즉, 나중에 게임을 하는 둘째 선수가 아무리 최선의 수를 둬도 첫째 선수가 이길 수 있는지 판단하라는 뜻이다. "첫째 선수는 반드시 이길 수 있습니다." 또는 "첫째 선수는 반드시 이길 수 있는 건 아닙니다."라고 판단 결과를 출력하라.
2. N의 값이 정해지고 첫째 선수가 수를 두었을 때, 첫째 선수가 반드시 이길 수 있는지 밝히라. 게임을 하나도 안한 생태와 비교했을 때, 판단 결과가 달라질 수도 있다.
3. N의 값이 정해지고 첫째 선수가 먼저 수를 두었을 때(임의의 연속한 종이 몇 장을 지웠을 때) 둘째 선수의 역을 맡아 게임을 진행하는 프로그램을 작성하라. 첫째 선수의 수는 키보드로 입력받는다. 수는 칸위치를 뜻하는L(1<=L<=N-K+1)의 값으로 정해진다. 이 수를 입력함에 따라 L부터 L+K-1 위치에 있는 칸이 지워진다. 그리고 사람이나 컴퓨터가 수를 둘 때마다 종이 조각의 상태를 1 2* 3* ... N과 같은 형식으로 출력한다. 각 번호가 출력되고 지워진 칸 번호 옆에만 별표를 출력하는 것이다.
게임이 끝나면 "첫째 (둘째) 선수가 이겼습니다."라고 출력한다. N과 K의 값은 게임을 하기 전에 입력받아 미리 정해지며, 입력받을 때는 "N>"과 "K>"처럼 프롬프트를 출력한다. 수를 입력받을 때 역시 "첫째 선수의 수>"와 같은 프롬프트를 출력한다. 또한 사용자가 입력한 내용이 올바른지 검사하도록 한다.
하드웨어를 제조. 판매하는 한 회사에서는 RISC 방식의 마이크로 프로세서를 개발했다. 이 프로세서는 문자열 자료형을 다룰 수 있으며, 문자열 안에 있는 특정 문자열을 다른 문자열로 바꾸는 기능을 제공한다.
이 프로세서는 기능을 수행하는 데 두 개의 메모리를 쓴다. 하나는 프로그램을 저장하는 메모리이며(찾을 문자열과 교체할 문자열의 집합), 또 하나는 처리를 수행할 입력 자료를 저장한다. 후자를 특별히 R이라고 부르겠다. 문자열 처리는 R에서 그대로 이루어지기 때문에 문자열 처리의 중간 결과 또는 최종 결과는 모두 R이라는 메모리에 들어있다. R은 크기 제한이 사실상 없다고 가정한다.
이 프로세서를 제어하는 프로그램은 PROLAN/M이란 언어로 작성된다. 언어에 대해 자세히 설명하기 전에 이 언어로 작성된 프로그램을 하나 예로 들어보겠다.
(aa,b) (ba,a) (bc,a) (c,start) (d,) (b,finish) (,)
"abcabcd"라는 문자열을 주어 이 프로그램을 돌리면 처음 문자열은 "finish"로 바뀐다. R의 상태는 다음과 같이 변한다.
abcabcd →aaabcd → babcd → abcd → aad → bd → b → finish
이제 PROLAN/M 언어의 문법을 구체적으로 살펴보자. A::=B는 "A는 B로 정의된다"란 뜻이며, 콜론은 "또는"을 의미한다.
처리할 입력 문자열이 R에 들어오면 프로세서는 R의 왼쪽 끝부터 오른쪽 끝까지 검색을 한다. 그리고 각 위치마다 <교환할 문자열 쌍의 나열>에 있는 <교환할 문자열 쌍>의 <좌측> 문자열이 이 위치에 있는지 대입한다. 있으면 그 문자열 쌍에 있는 <우측> 문자열로 그것을 교환한다. 교환하고 나면 검색 위치는 다시 맨 앞으로 되돌아가고, 대입해 보는 <교환할 문자열 쌍> 위치도 맨 처음으로 되돌아간다. (,)은 언어의 정의에서 알 수 있듯 프로그램의 끝을 의미할 뿐이며, 검색/치환 작업과는 무관하다. 이 작업을 더 이상 바꿀 문자열이 없을 때까지 반복한다. 더 바꿀 것이 없으면 현재 R에 있는 문자열이 최종 결과가 된다.
말이 어려워지는 것 같으니 위에서 언급한 예제 프로그램과 입력 문자열로 다시 설명하겠다. abcabcd의 맨 왼쪽 위치부터 차례대로 aa, ba, bc, c, d, b를 대입한다. 그러나 ab...로 시작하는 것은 없으므로 다음 위치로 간다. 다음 위치인 둘째 칸은 bc...로 시작하므로 bc가 있다. b→finish보다 bc→a가 앞에 있으므로 bc를 a로 바꾼다. aaabcd가 된다. 뒤에도 bc가 있으나 그냥 놔두고, 다시 문자열 맨 처음부터, <교환할 문자열 쌍의 나열> 역시 맨 처음 aa부터 다시 찾기 시작한다. 맨 앞에 aa가 있으므로 이를 b로 바꾸면 babcd가 된다. ba...부터 다시 시작하여 ba를 a로 바꾼다. abcd가 된다. ab...부터 또 검색을 시작한다. 이번에는 둘째 칸에 bc가 있으므로 이를 a로 바꾼다. 이런 식으로 찾기를 계산하면 aad는 bd로, bd는 d→공란이 적용되어 d가 없어진 b로, b는 다시 finish가 됨을 알 수 있다. finish에는 aa, ba, bc, c, d, b 중 어떤 문자도 포함하지 않으므로 더 바꿀 게 없다. 그러므로 finish가 최종 R의 값이며, 동시에 출력 결과가 된다. 이렇게 프로그램 실행은 끝난다.
1. '<자연수1>+<자연수2>=?'란 형식으로 된 문자열을 '<자연수1>+<자연수2>=<자연수3>'로 변환하는 PROLAN/M 프로그램을 작성하고 이를 디버그 하라. 자연수n은 물론 임의의 자연수를 나타내는 숫자로 된 문자열이다. 결과가 올바른 산술식이어야 함은 두말할 나위도 없다. 예를 들어 "1990+123=?"이라는 문자열은 프로그램 실행이 끝났을 때 "1990+123=2113"으로 변환되어야 한다. 이 코드는 SUM.PRM이란 이름으로 저장하라.
2. PROLAN/M 디버거를 제작하라. 디버거는 다음 기능을 갖추고 있어야 한다.
문제 1에 대한 점수는 코드를 작성하는 데 쓰인 <교환할 문자열 쌍>의 수(크기)와, 심사 위원들이 준비한 테스트 데이터를 답안 프로그램이 바꾸는 데 걸린 시간(속도)에 따라 결정된다. 심사 기준이 두 단계이므로 응시자는 각 기준에 맞게 최적화된 두 가지 정답을 준비해도 될 것이다. 작성된 PROLAN/M 코드는 주최측에서 대회용으로 제작한 PROLAN/M 런타임으로 테스트한다.
문제 2에 대한 점수는 모든 지시대로 프로그램을 제작했는지와 심사 위원의 테스트에 합격하는지의 여부에 따라 결정된다.
a와 n(n<100)이라는 정수를 입력받는다. 한편 대입문과 곱셈을 지원하는 프로그래밍 언어를 하나 상상해 보자. b=a^n라는 연산을 곱셈 횟수를 최소로 하여 그 언어로 구현하는 코드를 생성하는 프로그램을 작성하라. 아래는 n=13일 때의 예이며, { }는 주석을 나타낸다.
X1:=a; {=a}
X2:=X1*X1; {=a^2}
X3:=X2*X2; {=a^4}
X4:=X3*X1; {=a^5}
X5:=X3*X3; {=a^8}
X6:=X5*X4; {=a^13}
b:=X6;
한 미술관에는 여러 명의 경비원이 미술관을 지키고 있다. 한 경비원은 지정된 시각부터 임무를 맡기 시작하여 지정된 시간이 지나면 퇴근한다. 이러한 경비원들의 일정표를 보고 다음을 판단, 처리하는 프로그램을 작성하라.
(시간의 단위는 모두 정수 분이다.)
평면 위에 N개(N>0)의 선분이 있다. 각 선분의 끝점은 두 좌표쌍 (x1[i], y1[i])와 (x2[i], y2[i])로 표현된다.여기서i는1<=i<=N인 임의의 정수이다. 다음과 같은 기능을 하는 프로그램을 작성하라.
1. 다음과 같은 형식으로 문제를 푸는데 필요한 자료를 입력받는다.
N의 값은? ← 선분의 수 X1[1]--> Y1[1]--> X2[1]--> Y2[1]--> ← 각 선분의 좌표 X1[2]--> Y1[2]--> X2[2]--> Y2[2]--> ... X1[N]--> Y1[N]--> X2[N]--> Y2[N]-->
2. 평면 위에 놓인 선분 중 다른 선분과의 교점이 가장 많은 직선을 찾아라. 선의 끝점이나 시작점도 선의 일부이므로 다른 선과 이 점이 만나는 것도 교점이 있는 것으로 인정한다. 선분의 번호를 교점이 가장 적은 선분부터 많은 것의 순으로 정렬하여 출력하라.
1부터 N(N<=50)까지 번호가 매겨진 지점이 있다. 정점은 도로망으로 연결되어 있으며, 두 지점을 연결하는 길의 길이는 모두 1이다. 길은 이 지점들과만 연결되어 있으며, 두 길이 연결되어 교차로가 생기는 경우는 없다. 제 0시각에 이 지점 중 어느 곳에 로봇이 놓여 있다. 로봇의 대수(M)는 2대 또는 3대이며, 각기 다른 곳에 놓인다. 로봇들은 따로따로 한 지점에서 다른 지점으로 계속 움직인다. 움직이는 방식은 그래프 순회와 같다. 즉, 길에서는 도중에 방향을 바꾸지 못하며 한 지점에 도착해서 어느 길을 타고 다른 지점에 갈 지만 선택할 수 있다. 로봇은 멈춰 설 수 없고 끊임없이 움직여야 한다. 한 단위 시간동안 i째 로봇이 갈 수 있는 거리는 speed[i]이다. 이 값은 1 아니면 2이다.
이들의 목적은 가능한 한 가장 짧은 시간 안에 한 지점에서 다른 로봇들과 만나는 것이다. 모든 로봇들이 한 곳에 만나려면 로봇들이 가장 적합하게 움직였을 때 최소 얼마나 시간이 걸리겠는지 시간 T의 값을 구하는 프로그램을 작성하라. 만약 모든 로봇이 만나는 게 불가능하다면 "T>=0일 때는 만나는 것이 불가능함."이라는 메시지를 출력하라.
자료를 입력받는 형식은 아래와 같다. 도로가 연결하는 지점의 번호는 당연히 두 개의 숫자로 입력받아야 한다. 그리고 모든 수치는 음 아닌 정수이다.
N의 값: 길의 개수 K의 값: 1번 길이 연결하는 지점 번호: … K번 길이 연결하는 지점 번호: M의 값: 1번 로봇의 속도: … M번 로봇의 속도: 1번 로봇이 처음 있는 지점 번호: … M번 로봇이 처음 있는 지점 번호:
출력 형식은 다음과 같다.
"시간 = T" 또는 "T>=0일 때는 만나는 것이 불가능함"
직사각형 모양을 한 어떤 도시가 있다. 이 도시는 길거리가 바둑판 모양으로 잘 구성되어 현재 블록에서 다른 블록으로 갈 수 있는 길이 동서남북 네 갈래뿐이지만 울퉁불퉁한 지형에 위치해 있어서 거리의 각 블록마다 높이가 다르다. M×N 크기의 행렬 K[y, x]에는 해수면을 기준으로 한 각 구획의 높이가 들어있다.
/\ Y
|
M +---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+---+
. | | A| | | | |
. +---+---O---+---+---+---+
. | | | | | | |
+---+---+---+---+---+---+
| | | | |B | |
2 +---+---+---+---*---+---+
| | | | | | |
1 +---+---+---+---+---+---+--------->X
1 2 ... N
다음과 같은 처리를 하는 프로그램을 작성하라.