제 1회

첫 대회인 제 1회는 1989년 5월 16일부터 20일까지 불가리아 프라베쯔에서 열렸다. 컴퓨터의 사정이 지금보다 훨씬 뒤쳐져 있었고, 첫 대회여서 그런지 문제도 요즘 올림피아드 문제와 비교해 볼 때, 입출력 방법이나 처리 과정 규정이 매우 막연하고 엉성한 면이 있다. 프로그램을 작성하는 게 아니라 지필식으로 보이는 문제도 있다. 지시가 모호하고 입출력 예제도 없어 1, 2회 문제는 번역하기가 어려웠다. 그러나 난이도는 프로그래밍 공부하는 데 여전히 손색이 없기 때문에 문제가 확실하게 규정하지 않은 조건은 나름대로 독자가 가정해서 문제를 풀어보는 것도 괜찮을 것 같다. 특히 승강기 시뮬레이션 문제는 조건을 까다롭게 지정하고 9회 대회 때처럼 라이브러리를 이용하여 입출력하도록 했다면 상당히 어렵고 괜찮은 문제가 됐을 것이다.

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

1. 상자 옮기기

2. 승강기 조종

3. 책 돌려보기

4. 문장 암호화

5. 그래프 돌기

6. 정이십면체의 변

1. 상자 옮기기

서로 붙어 있는 2×N 개의 상자가 있다. (단, N<=5). 2개의 인접한 상자는 비어있고, 나머지 상자들 중 N-1 개는 A라는 문자를 담고 있고, N-1 개는 B라는 문자를 담고 있다. N=5인 경우 있을 수 있는 한 경우는 다음과 같다.

A B B A 　 　 A B A B

우리는 상자들을 옮겨 A를 담은 상자가 모두 B를 담은 것보다 앞에 오게 만들고 싶다. 이 때, 빈 상자는 두 개가 붙어있기만 하면 어디에 있건 상관없다. 즉, 다음과 같이 목표만 달성하면 된다.

[AAA..ABBBB]  [..AAAABBBB]  [AAAA..BBBB]  [AAAABBBB..]

한편, 상자를 아무렇게나 교환해서는 안 되고, 서로 붙어 있으면서 비어 있지 않은 두 상자를 비어 있는 두 상자와 교환하는 방법으로 옮겨야 한다. 상자 순서는 그대로 유지되어야 한다. AB라는 상자를 옮긴다면 AB를 동시에 그대로 빈 위치와 옮겨야지 BA로 옮기면 안 된다.

문제

다음과 같은 기능을 수행하는 프로그램을 작성하라.

  1. 먼저 상자의 수, 상자의 처음 상태, 교환할 위치들을 사용자에게서 키보드로 입력받게 해서, 교환 과정을 나타내 보이도록 한다. 교환할 위치는 현재의 빈 상자와 위치를 교환할 두 상자의 왼쪽 위치로 입력받는다. 이 수치의 범위는 1부터 N-1(한 번에 두 칸씩 교환하므로 N-1임)까지이다. 그리고 한 번 교환이 일어날 때마다 프로그램은 상자의 변화를 찾아내어 그것을 파악해서 상자의 상태를 표시해야 한다.
  2. 제시된 초기 상태에서 목표 상태로 만들려면 최소 한 번 이상 교환 작업을 해야 할 것이다. 어떤 위치를 교환해 나갈 지 그 과정을 계산하여 찾으라. 목표 상태로 만드는 게 불가능하거나 상자가 이미 목표 상태에 있다면 찾을 필요가 없다.
  3. 목표 상태로 만들려면 위와 같은 교환을 최소 몇 번 해야 하는지를 구하라.

2. 승강기 조종

어떤 건물의 각 층은 연속된 정수 0, 1, 2, ..., N (N<=15)로 되어 있다. 그리고 그 건물에는 K(1 K 4)개의 승강기가 있다. 모든 승강기의 관리는 승강기 제어기 한 곳에서 이루어지며 제어기는 버튼을 눌러서 들어온 2가지 명령을 받아들인다. 외부 버튼들은(올라가고 내려가는 버튼) 각 층마다 있으며, 승강기들이 모두 공유한다. 이는 승강기를 내려오거나 올라오게 하는 외부 버튼이 승강기마다 있는 게 아니라 버튼을 누름으로써 여러 개중 놀고 있는 승강기 하나를 자동으로 찾아오게 한다는 뜻이다. 다만 내부 버튼은(주어진 층으로 움직이게 한다) 승강기마다 안에 있다.

이 때, 아래와 같은 조건에 따라 승강기를 제어하는 것을 모델링하는 프로그램을 작성하라.

  1. 건물에 한 개의 승강기만 있다면, (K=1) 요구(사용자가 버튼을 누르는 것)를 한 번에 하나만 받아들인다. 다른 요구는 첫 번째 요구를 완수하고 나서 받아들인다.
  2. 그렇지 않고 건물에 승강기가 여러 개 있으면 (K>1) 각 승강기들은 다른 요구를 수행하고 있지 않을 때만 내부의 요구를 받아들인다. 승강기 제어기는 들어오는 여러 요구들을 동시에 등록할 수 있다. 내부 요구는 승강기 안에서 버튼 조작이 생긴 승강기에서 수행된다. 한편 제어기는 사람이 없는 적합한 승강기를 스스로 골라 외부 요구를 수행하게 한다.
  3. 2번과 같은 경우에서 제한 조건을 추가한다. 번호가 짝수인 승강기는 짝수 층에서만 서고, 홀수인 승강기는 홀수 층에서만 서도록 한다. 단, 0층에서는 모든 승강기가 설 수 있다.
  4. 3번과 같은 경우에서 각 승강기에서 대기중인 내부 요구가 둘 이상 여러 개 있을 수 있다고 가정하자. 그래도 모든 내부 요구는 승강기가 쉬고 있든 그렇지 않든 받아들여지고 등록된다.

추가 지시

한 시간 간격으로 각 승강기는 지정된 층에 있게 되며, 모든 승강기는 동시에 움직인다. 다음 시간 간격에 한 승강기는 한 층을 올라가거나 내려가거나 그대로 있을 수도 있다. 승강기 조작 요구(프로그램에 들어오는 입력)는 아무 간격일 때에나 받아들일 수 있어야 하며, 그 요구는 다음과 같은 종류가 있을 수 있다.

한 시간 간격 사이에 여러 개의 요구가 들어올 수도 있고 아무 요구도 없을 수도 있다. 또한 승강기는 충분히 크기 때문에 사람이 얼마든지 타도 좋다.

작성하는 프로그램은 승강기 제어를 가장 "지능적"으로 해야 할 것이다. 예를 들어 4층에서 위로 올라가는 버튼을 눌렀을 경우 가장 가까이 있는 승강기를 불러주는 것은 너무 당연한 일이고 더 나아가 만약 3층에서 올라오는 승강기(2번)가 있고 5층에 사람이 없어 멈추어 있는 승강기(4번)가 있다면 괜히 잘 올라가고 있는 2번을 세워서 태우는 것보다 5층에 있는 것을 불러다 주는 것이 더 나을 것이다. 다만, 위의 2번 승강기에 만약 4층에서 내리니 세워달라는 내부 명령이 있었다면 멈추어 있는 4번 승강기를 부르느니 이왕 4층에 멈추었다가 올라갈 2번 승강기를 불러주는 것이 더 나은 전략인 것이다.

그리고, 승강기 조작 전략, 즉 알고리즘에 대한 명백한 설명이 있어야 한다.

3. 책 돌리기

사람이 N명 든 집단이 있다. 집단에 있는 모든 사람 역시 집단에 있는 사람들 중에 N/2명 이상의 사람과 친구 관계이며, K명 이하인 적을 두고 있다. 집단에 있는 사람 중 한 명이 모두가 읽으면 좋은 책을 가지고 있다. 그래서 서로 돌려가며 책을 읽히려고 한다. 아래와 같은 조건을 만족하는 프로그램을 작성하라.

  1. 책을 전해주되, 친구 사이에 있는 사람에게만 주고, 그렇게 책을 돌려서 마지막에는 책의 소유자에게 돌려주는 방법을 찾으라. 모든 사람들은 꼭 한 번씩만 책을 받고, 건네주어야 한다.
  2. 책을 다 읽고 그것에 대해 토론을 할 수 있도록 사람들을 S개의 하위 집단으로 나누어라. 모든 사람은 그가 참여하는 하위 그룹에 적이 P명 이하가 있게 만들어야 한다.

단, S×P>=K라고 가정한다.

4. 문장 암호화

대문자 알파벳과 .(마침표) ,(쉼표) + - : / ? !의 여덟 가지 기호로만 구성된 문장이 있다. 이 문장들은 통신 채널을 통해 바이트의 나열로 보내진다. 각 바이트를 구성하는 비트에서 1의 개수는 항상 짝수여야 한다.

  1. 위의 문장을 이진 파일로 암호화하는 방식을 고안하라. 원래대로 복원이 가능하며 크기를 가능한 한 많이 줄일 수 있는 방법이어야 한다.
  2. 다음 처리를 하는 프로그램을 작성하라.

5. 그래프 돌기

정점이 n개이고 각각 연결된 변의 수가 3개인 그래프를 상상해 보자. 예를 들면 다음과 같다.

그래프의 정점 T가 정점 X, Y, Z와 변으로 하나씩 연결되어 있다고 생각해 보자. 이때 각 XTZ가 각 XTY보다 작으면 "X의 관점에서 봤을 때 Y는 T의 왼쪽에 있는 이웃 정점이며 Z는 오른쪽에 있는 이웃 정점이다."라고 규정하겠다. (단, 각도는 반시계 방향으로 측정하며, 양수로 표기한다.)

위의 그래프로 예를 들자면 A의 관점에서 봤을 때 E는 H에서 오른쪽에 있는 이웃 정점이며 G는 왼쪽에 있는 이웃 정점이다. 왜냐하면 각 AHE는 각 AHG의 크기보다 작기 때문이다.

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

  1. 그래프의 정점 좌표와 변을 입력받아 그래프 전체를 화면에 출력한다. 출력 형식은 프로그램이 알아서 적절하게 조절하며, 변은 직선으로 그리도록 한다.
  2. 정점 X0과 X1의 좌표와 L 또는 R로 이루어진 문자열을 입력받는다. 그런 뒤 프로그램은 그래프 상에서 X0, X1, X2, ..., Xn을 지나는 길을 찾아야 한다.
  3. 2번에서 찾아낸 경로를 화면에 그린다.
  4. 시작점과 끝점을 입력받아 두 지점 사이를 가장 가까운 길(=가장 적은 정점을 거쳐가는 길)로 연결한다. 이를 화면에 그리고, 이 길을 통해 시작점에서 끝점으로 순회하도록 하는 제어 문자열(2번 문제처럼 L, R로 방향을 지시하는 것)을 만들어서 출력한다.

6. 정이십면체의 면

정이십면체가 하나 있다. 각 면은 1부터 20까지 번호가 매겨져 있다. 우리는 이 정이십면체의 각 면을 한 번씩 둘러볼 수 있는 길을 정했으면 한다. 방문하는 데 드는 비용을 나타내는 C는 다음과 같은 합산식으로 결정된다.

fi는 i번째에 도달하는 면의 번호이다.

한 면에서 다른 면으로 지나가려면 두 면이 서로 접해 있어야 한다. 접해 있는 경우란, 두 면이 한 모서리 또는 꼭지점을 공유하는 경우를 일컫는다.

위와 같은 경우에 가장 비용을 적게 들이고 모든 면을 방문할 수 있는 길을 찾아라. 답을 잘 구하는 만족스러운 알고리즘을 찾아냈다 하더라도 시간이나 공간 복잡도에 걸려 정답보다 못할 수도 있음을 알아두자.