제 11회는 1999년 10월 9일부터 16일까지 터키에서 열렸다. 난이도가 다시 높아졌다. 문제마다 제한 시간이 다르고 매우 빠듯해진 것과, 99년 전국 대회처럼 부분 점수에 대해 명확하게 규정하고 있다는 것이 색다르다. 98년에는 빠졌던 인터랙티브 문제가 한 문제 다시 출제됐다. 문제당 100점 총점 600점 만점에 금메달 입상자의 최고 점수는 438점, 동메달 입상자의 최저 점수는 135점이었다.
원문이 있는 곳: http://olympiads.win.tue.nl/ioi/ioi99/contest/official/index.html
여러분은 운영하고 있는 꽃가게의 창가를 가장 좋은 방법으로 정리하려고 한다. 꽃가게에는 F개의 서로 다른 꽃이 있고, 꽃의 개수 이상인 꽃병들이 한 줄로 서 있다. 꽃병들은 선반에 붙어 있으며, 왼쪽부터 오른쪽으로 1, 2, ..., V까지 차례대로 번호가 매겨져 있다. 꽃은 아무 꽃병에나 꽂을 수 있으며 역시 1, 2, ..., F로 번호가 붙어 있다. 꽃병이 꽃보다 개수가 더 많으면 남는 꽃병은 비게 되며, 하나의 꽃병에는 하나의 꽃만 꽂을 수 있다. 그리고 중요한 규칙이 있는데, 번호가 작은 꽃은 반드시 번호가 더 큰 꽃보다 왼쪽에 있는 꽃병에 꽂아야 한다. 왼쪽부터 오른쪽으로 훑을 때 꽃병의 번호는 물론 꽃의 번호까지 오름차순을 유지해야 한다는 말이다.
각 꽃들은 실제 꽃들이 그런 것처럼 제각기 특성이 있다. 꽃을 어떤 꽃병에다 꽂으면 미적 가치가 정수 값만큼 생긴다. 어떤 꽃을 어떤 꽃병에 꽂느냐에 따라 얻게 되는 미적 가치는 다르다. 이 정보는 아래의 표처럼 제시된다. 단, 빈 꽃병의 미적 가치는 0이다.
|
꽃병 꽃 |
1 | 2 | 3 | 4 | 5 |
| 1 진달래 | 7 | 23 | -5 | -24 | 16 |
| 2 베고니아 | 5 | 21 | -4 | 10 | 23 |
| 3 카네이션 | -21 | 5 | -4 | -20 | 20 |
위의 표에 따르면 진달래는 2번 꽃병에 꽂으면 매우 아름답게 보이지만 4번 꽃병에 꽂으면 상당히 보기 싫어지게 된다.
창가 조경을 가장 아름답게 하려면 위에서 제시한 규칙을 지키면서 꽃들이 만들어낸 미적 가치의 합이 최대가 되어야 한다. 이럴 경우에는 1번 꽃을 2번 꽃병, 2번 꽃을 4번 꽃병, 3번 꽃을 5번 꽃병에 꽂으면 23+10+20이 되어 가장 아름다운 장면이 펼쳐진다. 최대값이 나오는 경우가 여러 가지가 있다 해도 그 중 한 가지만 출력하면 된다.
파일: flower.inp
첫 줄에는 꽃의 수 F와 꽃병의 수 V가 들어있다. 다음 F개의 줄에는 각각 V개의 정수가 있다. (i+1)째줄의 j째 수가 i번 꽃을 j번 꽃병에 넣었을 때의 미적 가치가 된다.
3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20
파일: flower.out
첫 줄에는 최대 점수를 출력한다. 둘째줄에는 F개의 정수를 출력한다. k째 정수는 k째 꽃이 꽃힐 병의 번호이다.
53
2 4 5
프로그램의 실행 제한 시간은 2초이다. 심사 때 부분 점수는 없다.
긴 문장 하나와 여러 개의 암호가 있다. 문장은 이 암호를 독특한(혹은 불분명한) 형태로 숨기고 있는 문자열이다. 문자열과 암호는 영어 알파벳으로만 되어 있으며, 대소문자가 구분된다. 한편, 문자열의 길이는 우리가 상식적으로 생각하고 있는 바와 같이 정의된다. 즉, ALL이라는 문자열의 길이는 3이다.
이 문장에는 불필요한 문자열이 섞인 채 암호가 띄엄띄엄 들어있다. 예를 들어 암호 ALL은 문자열 속에 AuLvL과 같은 식으로 들어있다. 여기서 u와 v는 임의의 문자열이다--L이나 A도 될 수 있도 있고, 빈 문자열일 수도 있다. 이 때 우리는 이렇게 정의한다: AuLvL은 ALL을 감싸는 문자열이라고. 일반적으로 '감싸는 문자열'이란 이와 같이 첫 번째 글자와 마지막 글자가 암호의 첫 글자 마지막 글자와 같으면서, 안에 있는 글자들의 일부를 지우면 암호로 만들 수있는 문자열이라고 정의를 할 수 있다. 한 문장 안에서 같은 암호를 감싸는 문자열은 여러 개가 있을 수 있으며, 또 아예 없을 수도 있다. 또한 감싸는 문자열 하나는 여러 암호를 감싸고 있을 수도 있음을 유의해야 한다.
감싸는 문자열은 시작 위치(첫번째 글자의 위치)와 끝 위치(마지막 글자의 위치)로 정의된다. 한편 문장에서 첫 번째 글자의 위치는 1이다. 감싸는 문자열 c1, c2가 있을 때, c1의 시작 위치가 c2의 끝 위치보다 크거나, 또 그 반대의 경우라면 c1과 c2는 겹치지 않는다고 규정한다. 만약 위 조건이 만족되지 않으면 c1과 c2는 서로 겹친다고 말한다.
문장 속에 숨겨진 암호를 조건에 맞도록 찾아내는 게 이번 문제이다. 다음 조건을 만족하는 '감싸는 문자열'을 문장 내에서 여러 개 찾아내는 프로그램을 작성하라.
최적해가 여러 개 있더라도 답안 프로그램은 한 가지 경우만 출력하면 된다.
한편, 암호 w를 감싸는 문자열 c가 있다고 하자. 이때 c안에 포함돼 있는 문자열 중, c의 끝 위치를 차지하지 않고도 w를 감싸는 것이 더 있을 수 없다면, c를 w의 오른끝이라고 일컫기로 한다. 예를 들어 w가 ALL이고 c가 AAALAL이라고 한다면 c는 w를 오른끝으로 감싼다고 간주할 수 있다. 하지만 c가 AAALALAL이라면 오른끝이 아니다. L로 끝나기는 했지만, L이 세개 있어서 c의 중간에 또 ALL을 감싸는 문자열이 생길 수 있기 때문이다.
입력 자료로 들어오는 문장은 다음 사실이 보장된다.
입력 파일에는 word.inp와 text.inp가 있다. word.inp의 첫 줄은 찾고자 하는 암호의 개수 N이 들어있고, 그다음 N개의 줄에는 각 줄마다 암호가 공백 없이 들어있다. 각 암호에는 암호를 구분하는 고유번호가 있는데, 암호의 고유번호는 암호가 word.inp에 수록된 순서대로 1부터 N까지 정해진다.
한편, text.inp는 암호를 감싸는 문자열을 여러 개 포함하는 문자열의 나열이 공백 없이 들어있다. 문자열의 나열은 줄바꿈 문자(아스키 13번과 10번)로 끝난다.
효율성을 위해, 입력 파일의 형식을 file 대신 text로 선언할 것을 권한다.
출력 파일 이름은 codes.out으로 한다.
첫 줄에는 얻은 답(문장 안에 있는 감싸는 문자열들 길이의 총합. 답안 프로그램이 구해낸 것)을 출력한다. 그다음에는 각 줄마다, 암호를 감싸는 문자열에 대한 정보를 세 개의 정수 i, s, e의 꼴로 출력한다. s는 이 감싸는 문자열의 시작 위치, e는 이것이 끝나는 위치이다. 마지막으로 i는 여기에 감춰져 있는 암호의 고유번호이다.
words.inp:
4
RuN
RaBbit
HoBbit
StoP
text.inp:
StXRuYNvRuHoaBbvizXztNwRRuuNNP
~~~~ ~~~~~~~~~~~~~ ~~~~~
codes.out:
12
2 9 21
1 4 7
1 24 28
출력 결과를 보면 이 문장속에 숨겨져 있던 암호는 "RuN RaBbit RuN"이 된다. 또 다른 답안으로는 "RuN HoBbit RuN"이 있을 수 있다. 암호 자체를 출력하는 게 아님을 유의하기 바란다.
프로그램의 실행 제한 시간은 10초이다. 부분 점수는 없다.
여러분은 지하 도시 중의 하나인 카파도치아의 내부에 갇혔다. 어둠 속에서 길을 찾아 헤매다가 우연히 이 지역의 지도를 발견하였으나, 불행히도 여기가 지도에서 어디인지를 나타내는 표시는 지도에 없다. 우리는 지하 도시를 지도와 대조하여 돌아다니면서 지도가 처음 발견된 위치를 알아내려고 한다.
도시의 지도는 정사각형 격자 모양이다. 각 칸은 다닐 수 있는 길('O') 아니면 막힌 벽('W')이다. 북쪽이 어디인지도 지도에 있고, 우리에게도 나침반은 있기 때문에 방향 판단을 정확하게 할 수 있다. 처음에 우리는 물론 길에 있다.
답안 프로그램은 start()라는 함수를 호출하는 걸로 문제 풀이를 시작한다. 그다음부터는 look()과 move()함수를 써서 도시를 돌아다닐 수 있다. look()은 방향('E', 'W', 'S', 'N'중 하나)을 인자로 받아, 지금 위치에서 각 방향에 길이 있는지 벽이 있는지(즉 이 쪽으로 움직일 수 있는지 없는지)를 되돌린다. 되돌림값은 'O' 아니면 'W'이다. 한편, move()는 역시 방향을 인자로 받아 그 쪽으로 사람을 한 칸 가게 한다. 위치가 바뀌는 것이다. look()으로 먼저 살펴보아 가려는 곳이 길이었다면 어디든지 갈 수 있으나, 벽이 있는 곳으로 사람을 움직이게 하는 건 중대한 실수를 범하는 꼴이 된다.
그래서 답안 프로그램은 이 두 함수만으로 지도를 훑어보면서, 처음에 우리가 있었던 위치 x(가로), y(세로)를 finish(x,y)함수로 보고해야 한다. 또한 look()함수를 될 수 있는 한 적게 호출해야 한다.
입력 파일은 under.inp라는 텍스트 파일이다.
첫째 줄에는 지도의 가로, 세로 크기가 들어있다. 다음에는 지도의 모양이 O와 W만으로 들어있다. 정수 데이터와는 달리, 지도의 각 칸을 나타내는 데이터 사이에는 공백이 없다.
5 8
WWWWW (5,8)
WWWOW
WWWOW
WOOOW
WOWOW
WOOWW
WWOOW
WWWWW
(1,1)
출력 파일은 없다. 답안 프로그램이 구한 초기 위치는 finish(x, y) 함수를 호출해서 보고하면 된다. 다음은 풀이 과정의 한 예이다. 매개변수와 리턴값은 모두 대문자이다.
start();
look('N'); // 리턴 값 = 'W'
look('E'); // 리턴 값 = 'O'
move('E');
look('E'); // 리턴 값 = 'W'
finish (3, 5);
다음 헤더 파일을 인클루드하고 under.obj를 프로젝트에 포함시킨다. 그러면 라이브러리의 함수를 쓸 수 있게 된다. 한편, 대형 메모리 모델을 쓰기 바란다. (주의: 이것은 대회 일반 규정을 무시한 것이다.)
#include "under.h"
void start (void); /* 가장 처음에 호출해야 함 */
char look (char);
void move (char);
void finish (int,int); /* 가장 나중에 호출해야 함 */
아래에 있는 tpu를 포함시키고 나면 라이브러리의 함수를 쓸 수 있게 된다.
uses undertpu.tpu;
procedure start; { 가장 처음에 호출해야 함 }
function look (dir:char):char;
procedure move (dir:char);
procedure finish (x,y:integer); { 가장 나중에 호출해야 함 }
프로그램의 실행 제한 시간은 5초이다. 만점(A점)을 받으려면 답을 구하는 과정에서 look()을 채점 프로그램이 지정한 횟수 M번과 같거나 그보다 적게 호출해야 한다.(x번 호출했다고 하자.) 다만, M은 최적해(이론적으로 얻을 수 있는 가장 적은 횟수)보다는 항상 더 큰 값으로 잡히기 때문에, 답안 프로그램이 사방을 둘러보는 순서(시계 방향 또는 반시계 방향)과는 관계없이 알고리즘만 좋으면 충분히 좋은 점수를 얻을 수 있게 되어 있다.
그렇지 않다면 다음과 같은 공식대로 부분 점수를 얻게 된다.
풀이 도중 답안 프로그램이 올바르지 않은 동작을 취하면 그 답안의 점수는 0점이 된다.
딩지빌 시의 교통 체계는 특이하게 되어 있다. 도시에는 교차로가 있고, 교차로를 잇는 도로들이 있다. 두 교차로 사이에는 최소한 도로가 하나 이상은 있다. 교차로에서 자기 자신으로 돌아오게 하는 도로는 없다. 어떤 도로를 지나 한 교차로에서 다른 교차로로 가는 데 걸리는 시간은 상행선과 하행선이 모두 같다. 모든 교차로에는 신호등이 있으며 항상 파란불 아니면 빨간불 중 한 상태를 나타내고 있다. 각 색깔은 주기적으로 바뀌는데, 빨간불을 보이는 시간과 파란불을 보이는 시간은 실제 신호등이 그렇듯이 서로 다르다. 자동차가 한쪽 교차로에서 다른쪽 교차로로 가려면 출발하는 순간에 두 곳의 신호등 불 색깔이 모두 같아야 한다. 신호등의 불이 바뀌는 순간이 자동차가 목적지 교차로로 도착한다면 이 때 그 교차로의 신호등의 불은 바뀐 뒤의 상태라고 간주한다. 자동차는 한 교차로에서 멈춰 서 기다리고 있을 수도 있다. 이제 우리는 다음과 같은 정보를 보여주는 도시 지도를 받게 된다.
이번 문제는 자동차가 초기에 한쪽 정점(교차로)에서 출발하여 지정된 정점으로 가는 가장 빠른 길을 찾는 것이다. 가장 빠른 길이 여러 개 있을 수 있더라도 하나만 찾으면 된다.
파일 이름: lights.inp
첫째줄에는 자동차가 처음 있는 교차로의 번호, 가고자 하는 교차로의 번호 이렇게 두 숫자가 있다. 둘째줄에는 N과 M값을 나타내는 두 수가 있다. 그다음N줄에는 N째 교차로에 대한 정보가 들어있다. 각 줄마다 Ci, ric, tiB, tiP가 차례로 들어있는데, Ci란 이 교차로 신호등이 초기에 나타내고 있는 불빛 색깔이다. B 아니면 P이다.
그리고 다음에는 각 도로의 정보를 나타내는 M개의 줄이 뒤따른다. 각 줄에는 i, j, lij가 들어있다. 즉 교차로 i와 j가 도로로 연결돼 있으며, 이 사이를 지나는 데 걸리는 시간이 이와 같음을 나타내는 것이다.
파일 이름: lights.out
첫째 줄에는 이 답안대로 자동차를 몰 때 걸리는 시간을 출력한다. (물론 때에 따라서는 신호가 바뀔 때까지 어떤 교차로에서 기다리는 시간도 있게 되므로 이를 고려해야 한다.)
둘째 줄에는 거쳐가는 교차로의 번호를 순서대로 출력한다. 따라서 가장 첫째 숫자는 자동차가 처음 있는 교차로의 번호이고, 마지막 숫자는 목적지 교차로의 번호여야 한다.
하지만, 두 교차로 사이를 가는 길이 없다면 파일 첫째 줄에 0만 출력하도록 한다.
lights.inp
1 4
4 5
B 2 16 99
P 6 32 13
P 2 87 4
P 38 96 49
1 2 4
1 3 40
2 3 75
2 4 76
3 4 77
lights.out
127
1 2 4
프로그램의 실행 제한 시간은 2초이다. 부분 점수는 없다.
줄 N개를 나란히 세워두고 하는 1인용 게임이 있다. 각 줄에는 블록이 0개 이상 끼워져 있으며, 1부터 N까지 번호가 매겨져 있다. 이중에 한 줄을 골라(p째 줄이라 하자)를 m이라는 숫자만큼 동작을 취하는 걸로 게임은 진행된다. 이렇게 되면 p째 줄에 쌓여 있던 블록 m개는 그 줄과 이웃하고 있는 p-1째 줄과 p+1째 줄로 옮겨진다. 아래 그림을 보면 이해가 될 것이다. 따라서 이 동작을 취하려면 p째 줄에 최소한 2×m개만큼 블록이 있어야 한다. 물론, p가 1이거나 N이어서 이웃이 하나밖에 없다면 블록이 m개만 있어도 된다.
이 게임의 목적은 이러한 동작을 반복하여, 각 줄에 있는 블록 수가 모두 같도록 상태를 바꾸는 것이다. 물론 동작 횟수는 최소로 해야 할 것이다. 최적해가 여러 개 있더라도 한 가지 방법만 골라서 출력하면 된다.
그림 설명: 블록이 0, 7, 8, 1, 4개씩 있던 줄에 p=2, m=2를 취하면, 줄의 상태는 오른쪽과 같이 변한다.
채점 때 쓰이는 입력 파일들은 최대 10,000번 이하의 동작으로 반드시 평평하게 할 수 있다.
2 <= N <= 200이고 0 <= Ci <= 2000. Ci는 초기에 i째 줄에 있는 블록의 개수를 나타낸다.
파일 이름: flat.inp
첫째 줄에는 N의 값이 들어있고 둘째 줄에는 각 줄에 초기에 들어있는 블록 개수가 들어있다. 둘째 줄에 있는 N개의 숫자들은 공백으로 구분한다.
5
0 7 8 1 4
파일 이름: flat.out
첫째 줄에는 기본 동작의 총 횟수 M을 출력하고, 그 다음 M개의 각 줄에 한 동작을 표현하는 두 정수 p와 m을 출력한다.
5
5 2
3 4
2 4
3 1
4 2
프로그램의 제한 실행 시간은 3초이다. 답안 프로그램이 구한 총 동작 횟수가 x, 채점 프로그램이 지정한 동작 횟수가 B라고 하자. 각 채점 데이터에 대해 만점을 받으려면 x가 B보다 작아야 한다. 물론 B는 꼭 이론적인 최적해의 동작 횟수를 나타내는 건 아니다. 사실 B의 값은 간단한 알고리즘으로 구해낸 최소 동작 횟수와, 각 줄에 있는 블록 갯수의 평균에 따라 결정된다.
이 문제는 부분 점수가 있다. 만점을 A점라고 하면 점수는 다음과 같이 산출된다.
딩지빌 주민들이 비행장을 건설하기 위한 부지를 결정하려고 한다. 이 지역 전체의 지도는 정사각형 칸으로 되어 있는데, 지도에는 각 위치의 고도가 수록돼 있다. 문제는 아래의 조건을 만족하면서 면적이 최대(즉, 정사각형 칸을 가장 많이 차지하는)인 직사각형 영역을 찾는 것이다.
만족하는 영역이 하나 이상이더라도 한 개만 출력하면 된다.
파일 이름: land.inp
첫 줄에는 U, V, C가 들어있다. 그 다음 V개의 줄에 x=1, ..., U에 대한 정수 Hxy가 들어있다. 자세히 말하면 Hxy는 입력 파일의 (V-y+2)째 줄에서 x째 수이다.
파일 이름 : land.out
찾은 영역의 위치를 나타내는 4개의 정수 Xmin, Ymin, Xmax, Ymax를 표시한다. 남서쪽 좌표와 북동쪽 좌표를 출력하는 것이다.
프로그램의 실행 제한 시간은 130초이다. 심사 때 부분 점수는 없다.