제 12회는 2000년 9월 23일부터 30일까지 중국 베이징에서 열렸다. 99년보다 문제가 쉬운 편이었다. "부분점수을 인정하는 일부 문제, 매우 빠듯해진 제한 시간, 라이브러리를 쓰는 문제"라는 양식이 작년과 마찬가지로 이번에도 적용됐다. 부분점수도 단순한 비율로 주는 게 아니어서, 최적해에서 조금만 오차가 생겨도 점수가 큰 폭으로 줄어들었다.
각 문제당 100점에 기본 점수 100점이 더해져 700점 만점이었으며, 러시아에서 만점자가 한 명 나왔다. 그리고 동메달 입상자의 최저 점수는 248점이었다.
원문이 있는 곳: http://olympiads.win.tue.nl/ioi/ioi2000/contest/index.html
좌우 같은 말이란 글자가 좌우 대칭을 이루고 있어서, 왼쪽부터 읽으나 오른쪽부터 읽으나 같은 의미가 되는 말을 일컫는다. 어떤 문자열이 있는데, 여기 아무 위치에 글자를 몇 자 더하여 이 문자열을 좌우 같은 말로 만들려고 한다. 방법이야 어떻든 최소한 몇 자를 더해야 이 문자열을 좌우 같은 말로 만들 수 있는지 계산하는 프로그램을 작성하라.
예를 들어 "Ab3bd"란 문자열은 글자 두 자를 적당한 곳에 끼워넣어서 "dAb3bAd", "Adb3bdA"와 같은 꼴로 좌우 같은 말로 만들 수 있다. 하지만 두 자보다 글자를 적게 넣어서는 좌우 같은 말을 만들 수 없다.
파일 이름은 palin.in이다.첫째줄에는문자열의길이N(3<=N<=5000)이 들어있고, 둘째줄에는 길이가 N인 문자열이 들어있다. 문자열에는 알파벳 대소문자와 숫자(0~9)가 들어있다. 대소문자는 구분하도록 한다.
5
Ab3bd
파일 이름은 palin.out이며, 입력된 문자열을 좌우 같은 말로 만들기 위해 더해야 하는 문자 개수의 최소값을, 첫째줄에 출력하면 된다.
2
만리 장성 옆에 있는 주차장에는 자동차들이 한 줄로 길게 늘어서 있다. 줄의 한쪽 끝을 왼쪽, 다른 끝을 오른쪽이라 일컫는다. 여러 종류의 차가 있으며, 종류가 같은 차가 여러 대 있을 수도 있다. 각 차의 차종은 정수로 구분된다.
일꾼 여러 명이 차들을 차종별로 오름차순으로 재배열하려고 한다. 일꾼들은 동시에 저마다 다른 차를 몰아 다른 일꾼이 차를 빼낸 곳에 자기 차를 세운다. 그렇게 해서 일꾼이 몬 차들의 위치가 제각기 바뀌는 과정을 한 '과정'이라 한다. 물론 매 과정마다 모든 일꾼이 차를 몰아야 할 필요는 없다. 필요한 차만 옮기면 되니까. 우리는 될 수 있으면 작업을 적게 해서 차들을 정렬하고 싶다.
N은 차량의 수이고, W는 일꾼들의 수이다. 줄서서 세워져 있는 각 자동차의 차종과 일꾼의 수를 입력받았을 때, 이 '과정'을 가장 적은 횟수만큼 수행하는 방법을 찾는 프로그램을 작성하라. 이 횟수는 많아야 [N/(W-1)]이 되며,(N/(W-1)을 반올림한 것) 절대 이보다 크지 않다.
다음과 같은 예를 생각해 보자. 4종류의 차 10대가 다음과 같이 세워져 있다.
2 3 3 4 4 2 1 1 3 1
일꾼이 4명이라면 작업을 세 번 해서 차들을 정렬할 수 있다.
2 1 1 4 4 2 3 3 3 1 (1회, 일꾼 4명이 작업)
2 1 1 2 4 3 3 3 4 1 (2회, 일꾼 3명이 작업)
1 1 1 2 2 3 3 3 4 4 (3회, 일꾼 3명이 작업)
입력 파일 이름은 car.in이다. 첫 줄에는 정수가 세 개 들어있으며, 각각 자동차의수N(2<=N<= 20000), 자동차 종류의개수M(2<=M<= 50), 일꾼의수W(2<=W<=M)를 나타낸다. 각 차종은 1부터 M까지의 정수로 구분되며, 차종별로 자동차가 적어도 한 대씩은 있다. 둘째줄에는 N개의 숫자가 있으며, i째 숫자는 왼쪽부터 시작해 i째 자동차의 차종을 나타낸다.
10 4 4
2 3 3 4 4 2 1 1 3 1
출력 파일 이름은 car.out이다. 첫 줄에는 찾아낸 과정의 총횟수 R을 출력한다. 그리고 다음에는 1부터 R회까지 행해지는 구체적인 정렬 과정을 R줄에 걸쳐 출력한다. 각 줄에 있는 첫째 숫자는 이 과정에서 위치가 바뀌게 되는 자동차의 수 C이다. 그리고 다음에는 2C개의 숫자가 뒤따른다. 각 쌍은 위치를 바꾸고자 하는 자동차가 있는 위치와, 그 자동차가 이동할 위치를 나타낸다. 위치는 왼쪽부터 시작해서 1부터 N사이의 정수로 표현된다. R개의 줄에 대해서 자동차를 옮기는 방법이 여러 개 존재할 수 있어도 한 가지 방법만 출력하면 된다.
3
4 2 7 3 8 7 2 8 3
3 4 9 9 6 6 4
3 1 5 5 10 10 1
답안 프로그램이 계산해 낸 '과정'의 횟수가 R회라고 하고, [N/(W-1)]이 Q라고 하자. R회만큼 행해지는 각 과정이 정확하게 출력이 되어 있지 않거나, 자동차들이 그 과정을 거쳐도 완전히 정렬되어 있지 않으면 그 데이터의 점수는 0점이 된다. 그렇지 않으면 점수는 다음과 같이 계산된다.
1부터 N까지 번호가 붙여진 N개의 물체를 대상으로 우주 실험이 행해지고 있다. 단, N은 홀수이다. 각 물체는 제각기다른고유한밀도Y(1<=Y<=N)를 지니고 있다. 밀도가 중간값인 물체란 자기보다 가벼운 물체의 개수와 자기보다 무거운 물체의 개수가 같은 물체를 가리킨다.
이번 문제는 1부터 N째 물체 중에 밀도가 중간값인 물체(즉, 밀도가 (N+1)/2인 것)가 몇째 물체인지 찾아내는 것이다. 그런데 불행히도 각 물체의 밀도를 알아내는 장비가 여의치 않아, 임의로 고른 세 물체 중에 밀도가 중간인 것을 판별해 주는 장치가 전부다. 우리는 이것만을 써서 이 판별기를 최소한으로 쓰고 전체 물체 중에 밀도가 중간인 것을 찾고자 한다.
함수가 세 개 들어있는 라이브러리가 제공된다. 이것을 써서 프로그램을 만들도록 한다.
device 라이브러리는 median.out, median.log라는 파일을 생성한다. median.out에는 두 줄에 정수가 하나씩 들어있게 되는데, 첫줄에 있는 것은 답안 프로그램이 Answer함수로 보고한 정답의 번호이다. 둘째줄에 있는 것은 답안 프로그램이 Med3함수를 호출한 횟수이다. 답안 프로그램이 라이브러리와 연락한 내용은 median.log에 모두 기록된다.
파스칼 사용자: 소스 코드에 다음 들임문을 넣도록 한다.
uses device;
C/C++ 사용자: 다음 전처리문을 소스 코드에 넣고, median.prj를 생성하여 median.c(median.cpp)와 device.obj를 같이 링크하도록 한다.
#include "device.h"
수험자는 device.in이라는 파일을 직접 만들어서 답안 프로그램이 라이브러리와 동작하는 모습을 확인할 수 있다. 라이브러리가 읽어들이는 내용은 두 줄이다. 첫 줄에는 물체의 개수 N을 지정하고, 다음줄에는 1부터 N째 물체의 밀도를 나타내는 N개의 정수를 넣도록 한다.
device.in
5
2 5 4 3 1
다음은 여기에 대해 라이브러리를 올바르게 5번 호출한 예이다.
파스칼 라이브러리 파일 이름: device.tpu
function GetN: integer;
function Med3(x,y,z:integer):integer;
procedure Answer(m:integer);
C/C++ 라이브러리 파일 이름: device.h, device.obj (대형 메모리 모델을 쓰도록 한다.)
int GetN(void);
int Med3(int x, int y, int z);
void Answer(int m);
큰길이 직선으로 쭉 뻗어있고, 길 옆으로 여러 마을이 자리잡고 있다. 이 문제에서 큰길은 정수가 늘어서 있는 수평선이고, 각 마을의 위치는 수평선 위의 한 점으로 표현된다. 마을들의 좌표가 겹치는 경우는 없다. 두 마을 사이의 거리는 수평선상에 있는 좌표의 차이의 절대값으로 정의된다.
우리는 이들 마을이 있는 곳에 우체국을 몇 곳 지으려고 한다. 물론 모든 마을마다 다 짓는 건 아니다. 전체 마을 중 몇 곳을 골라, 그 위치에만 우체국을 짓게 된다. 그리고 우리는 각 마을과 그 마을과 가장 가까운 우체국 사이의 거리의 합이 최소가 되게 하고 싶다.
각 마을의 위치와 짓고자 하는 우체국 개수를 입력받는다. 그래서 각 마을과 그 마을과 가장 가까운 우체국 사이 거리의 합으로 있을 수 있는 최소값을 계산하고, 그런 결과를 낼 수 있도록 각 우체국을 지을 위치를 출력하는 프로그램을 작성하라.
제한 시간은 2초이다.
입력 파일 이름은 post.in이다. 첫 줄에는 숫자가 두 개 있으며, 각각마을의수V(1<=V<= 300)와 짓고자 하는우체국수P(1<=P<=30, P<= V)를 나타낸다. 다음줄에는 각 마을의 위치를 나타내는 V개의 정수 좌표가 나온다. 좌표는 오름차순으로 정렬되어 있다. 각 좌표X의범위는1<=X<=10000이다.
10 5
1 2 3 6 7 9 11 22 44 50
출력 파일 이름은 post.out이다. 첫째줄에는, 각 마을과 거기서 가장 가까운 우체국 사이 거리들의 합의 최소값을 나타내는 정수 S를 출력한다. 다음 줄에는 우체국을 지을 마을을 골라, 그 마을의 위치를 나타내는 P개의 정수를 오름차순으로 출력한다.
9
2 7 22 44 50
답안 프로그램이 출력해 낸 최소값이 S이고 실제로 가장 작은 최소값(최적해)이 Smin이라면, 점수 c는 아래 표에 나온 대로 매겨진다.
| q=S/Smin | q=1.0 | 1.0<q<=1.1 | 1.1<q<=1.15 | 1.15<q<=1.2 | 1.2<q<=1.25 | 1.25<q<=1.3 | 1.3<q |
| c | 10 | 5 | 4 | 3 | 2 | 1 | 0 |
하지만, 출력 파일이 출력 조건을 지키지 않으면 그 데이터에 대한 점수는 0점이 된다.
어떤 나라에는 커다란 담장이 여러 개 건설되어, 한 담장의 양 끝은 정확히 두 마을과 연결이 돼 있다. 이 문제에서 마을은 점으로, 담장은 마을을 연결하는 선으로 표현된다. 담끼리 교차하는 경우는 없다. 그래서 이 나라는 담장 때문에 국토가 여러 "구역"으로 나눠지게 되는데, 한 구역에서 다른 구역으로 가려면 마을을 통과하거나 담을 넘어야 한다. 각 담장들은 모두 서로 이어져 있기 때문에 임의의 마을 A와 B에 대해서 한쪽 끝이 A이거나 B인 담장이 반드시 존재하며, 고립돼 있는 마을이 없다. 또한 담장만 따라 걸어가면 A에서 B까지 갈 수 있다.
이들 마을에 사는 사람들을 대상으로 하는 모임이 하나 있다. 각 마을마다 최대 한 명이 모임에 가입해 있으며, 모임에 가입한 사람이 한 명도 없는 마을도 있다. 그런데, 모임에 든 사람들이 마을 바깥에 있는 한 구역에서 만나고 싶어한다. 여기 회원들은 자전거를 타고 그 약속장소로 가는데, 교통 문제 때문에 마을을 통과하지 않으려 한다. 그리고 가는 과정에서 담장은 가능한 한 적게 넘고 싶다. 이들은, 도착하기 위해 각 회원들이 담장을 넘어야 하는 횟수의 합이 가장 적게 되는 곳을 찾아 거기서 모이기를 원한다.
마을은 1부터 N까지 번호가 매겨져 있다. (N은 마을의 총 개수) 그림 1을 보면, 정점은 마을을 나타내고, 정점들을 잇는 선은 담장을 나타낸다. 그리고 모임에 든 사람은 3번, 6번, 9번 마을에 한 사람씩 있다고 가정하자. 이때, 이 사람들이 전체적으로 담장을 가장 적게 거쳐서 모일 수 있는 적합한 곳은 그림 2에 나타나 있는 구역이다. 각 마을 사람이 화살표 친 대로 이동하면 되는 것이다. 담장을 넘은 총횟수는 2이다. 6번 사람이 4번과 7번 마을 사이에 있는 담을 넘어야 하고, 9번 사람이 2번과 4번 마을 사이에 있는 담을 넘었기 때문이다.
마을과 담장, 그리고 모임에 속한 사람들에 대한 자료를 입력받아, 모이기에 가장 적합한 구역을 고르고 담장을 넘는 총횟수의 최소값을 구하는 프로그램을 작성하라.
제한 시간은 2초이다.
입력 파일 이름은 walls.in이다. 첫째줄에는 구역의개수M이있다(2<=M<= 200). (그림 1을 살펴보면 생겨난 다각형 개수가 경계 바깥을 포함해서 10개임을 알 수 있다. 그 개수를 일컫는다.) 둘째줄에는 마을(그림에서 꼭지점)의개수N이있다(2<=N<= 250). 셋째줄에는 모임에 든 회원의수L이들어있다(1<=L<=30, L<=N). 그리고 넷째줄에는 각 회원이 사는 마을의 번호를 나타내는 L개의 정수가 오름차순으로 들어있다.
그리고 다음에는 2M개의 줄이 있으며, 한 구역에 대한 정보가 두 줄에 걸쳐 들어있다. 거기서 첫줄에는 이 구역이 감싸는 마을의 개수 I가 들어있으며, 다음줄에는 이 구역의 경계를 이루는 마을 I개의 번호가 시계 방향 순서로 들어있다. 다만, 한 가지 예외가 있는데, 가장 마지막에 있는 구역은(M째 구역) 마을 전체의 바깥을 이루는 구역에 대한 정보이다. 이 구역을 다룰 때만은 가장 바깥을 감싸고 있는 마을들의 번호가 반시계 방향 순서로 제시된다. 이렇듯 입력 파일에는 담과 마을로 인해 생겨난 모든 구역에 대한 정보가 바깥쪽 구역까지 포함헤서 모두 들어있다.
구역은 입력 파일에 수록돼 있는 순서가 곧 그 구역을 지정하는 번호가 된다. 가장 먼저 나오는 구역이 1번 구역, 그 다음에 있는 구역이 2번이다. 즉, 모이기에 가장 적합한 구역을 가리킬 때는 입력 파일에서 몇째로 나온 구역인지를 출력하면 된다.
10 10 3 3 6 9 3 1 2 3 3 1 3 7 4 2 4 7 3 3 4 6 7 3 4 8 6 3 6 8 7 3 4 5 8 4 7 8 10 9 3 5 10 8 7 7 9 10 5 4 2 1
출력 파일 이름은 walls.out이다. 첫째줄에는 답안 프로그램이 구한 총횟수의 최소값을 출력한다. 둘째줄에는 담장을 가장 적게 넘고 만날 수 있는 구역의 번호를 출력한다. 그런 구역이 여러 개 있을 수 있더라도 한 곳만 출력하면 된다.
2
3
단위 정육면체란 꼭지점이 x, y, z축으로 정수 좌표를 가지며, 크기가 1x1x1인 정육면체를 말한다. 두 정육면체가 면을 공유한다면 이 둘은 서로 접한다고 말한다. 서로 접하는 단위 정육면체가 여럿이 모이면 조형물이 된다. 조형물의 부피는 이것을 이루고 있는 단위 정육면체들의 개수와 같다.
그리고 블록이란 개념이 나오는데, 블록이란 부피가 최대 4인 조형물이다. 두 블록이 있는데 한 블록을 평행이동하거나 회전시켜서 다른 한쪽과 합동을 이룰 수 있다면 두 블록은 모양이 같다고 일컫는다. (다만 좌우 바꾸기는 포함되지 않는다.) 기본 블록은 아래 그림과 같이 12가지 종류가 있다. 그림에서 색깔은 모양 파악의 편의를 위해 넣은 것일 뿐이며 그 밖에 특별한 의미는 없다.
기본
블록 12가지
여러 종류의 블록이 있어 이 전체를 D라고 하자. D에 있는 모든 블록을 적당하게 쌓고 배치해서 S라는 조형물을 만들 수 있다면, 집합 D는 S의 밑바탕이라고 일컫기로 한다. 실제로 블록을 쌓을 때와 마찬가지로, 어떤 칸에도 두 블록의 정육면체가 서로 겹치지 않아야 한다. 이때, 한 종류의 블록을 두 번 이상 쓸 수 있다.
이번 문제는 기본 블록과 어떤 조형물 S에 대한 정보를 받았을 때, 블록을 가장 적게 써서 S를 만들 수 있는 밑바탕을 찾는 것이다. (종류가 아니라 개수이다. 종류를 가장 적게 쓴다면 1번 블록만으로 어떤 조형물도 만들 수 있을 것이다. 하지만 이렇게 하면 개수는 S의 부피만큼 나가게 될 것이다.) 문제가 복잡한 것 같지만 실질적으로 이 조형물을 만드는 과정을 구체적으로 출력하지는 않아도 된다. 쓰인 블록에 대해서 쓰인 횟수만큼 그 기본 블록의 번호만 출력하면 된다.
제한 시간은 6초이다.
우리는 단위 정육면체의 좌표를 이것의 여덟 꼭지점 중 x+y+z값이 최소인 것 하나의 좌표로 대표해서 나타내고자 한다. (쉽게 받아들이면 된다. 정육면체 하나를 한 점이라고 보자고 한 것임.)
기본 블록에 대한 정보를 담고 있는 파일 이름은 types.in이다. 이 파일의 내용은 아래에 나와 있으며, 12가지 기본 블록을 가지고 모든 데이터 파일에 대해 똑같은 내용으로 심사받는다. 다시 말해 기본 블록은 위에서 소개된 12가지가 전부이며, 불변이다. 첫째줄에는 이 블록의번호I가들어가며(1<=I<= 12), 둘째줄에는 이블록의부피V(1<=V<=4)가 들어있다. 다음 V줄에는 이 블록을 이루는 단위 정육면체의 좌표가 x y z 순으로 들어있다. (1<=x, y, z<=4) 이런 식으로 I가 1부터 12까지 열두 개 블록의 정보가 들어간다.
만들고자 하는 조형물을 담고 있는 입력 파일은 block.in이다. 첫째줄에는 이조형물의부피V(1<=V<=50)가 들어있다. 다음 V줄에는 이 조형물을 이루고 있는 단위 정육면체의 x, y, z 좌표가 들어있다. (1<=x, y, z<=7)
출력 파일 이름은 block.out이다. 첫째줄에는 기본 블록을 가장 적게 쓰고 본 조형물을 만들 수 있는 개수 M을 출력한다. 둘째줄에는 거기에 해당하는 M개의 기본 블록 번호를 차례대로 출력한다. 한 입력 파일에 대해 여러 정답이 있을 수 있지만 한 가지만 찾아 출력하면 된다.
기본 블록 12가지의 생김새를 표현한 types.in의 내용을 봅니다.
block.in
말(동물)의 모양을 표현한 조형물의 예
18 2 1 1 4 1 1 2 3 1 4 3 1 2 1 2 3 1 2 4 1 2 1 2 2 2 2 2 3 2 2 4 2 2 2 3 2 3 3 2 4 3 2 4 2 3 4 2 4 4 2 5 5 2 5
block.out
5
7 10 2 10 12
둘째줄에는 위와 같은 경우 외에도 다음과 같은 정답이 더 있을 수 있다.
2 7 10 11 12
2 7 11 11 12
4 4 7 10 11
4 4 9 10 11