제 16회

제 16회는 2004년 9월 11일부터 18일까지 그리스 아테네에서 열렸다. 같은 장소에서 IOI가 다시 개최되기는 그리스 아테네가 처음이다(1991년에 열린 제 3회). 이번 대회에서 쓰인 하드웨어 환경은 램 512MB, 3GHz인 펜티엄 4로, 해마다 성능이 향상되고 있다. 이제 rhide(통합 개발 환경)와 GCC와 Free Pascal 컴파일러는 IOI에서 필수 도구로 자리잡은 듯 하다.

그리스 신화 분위기를 물씬 풍기는 문제 내용이 이색적이다. 풀이법으로 다이나믹을 응용한 문제들이 주류를 이루나 꽤 어려운 것도 눈에 띈다. 특히 3번 다각형 분해 문제는 본디 NP-complete 문제인 것을 특수한 전제 조건을 주어 제출형으로 출제한 것이다. 모든 경시 문제들이 테스트 케이스를 푸는 제한 시간은 1초였으며, 메모리 제한은 16MB에, 4번만 128MB였다. 출력 형식이 비교적 단순했으며, 부분 점수 없이 여섯 문제 모두 최적해를 구했느냐 못했느냐의 여부에 따라 채점되었다.

입력 크기의 제한 조건에 단순한 최악 상황의 한계뿐만 아니라, 전체 테스트 중 절반이 속하는 "완만한" 환경에 대해서도 언급하고 있는데, 이는 문제를 완전히 풀지 못해 비효율적인 알고리즘을 쓰더라도, 이런 환경에 대해서라도 1초 안에 올바른 답을 출력하는 프로그램을 최선을 다해 만들어 보라는 주최 측의 배려로 보인다.

우리나라는 이번 대회에서 금메달 하나, 은메달 둘을 획득해 비공식(국가별 순위를 주최측에서 공식 집계하지는 않는다) 종합 순위 9위를 차지했다. 문제당 100점에 총 600점 만점으로, 금메달 입상자의 최고 점수는 565점, 동메달 입상자의 최저 점수는 265점이었다.

원문이 있는 곳: http://www.ioi2004.org/html/competition_test1.html

1. 아르테미스

2. 헤르메스의 심부름

3. 다각형 분해 (제출형)

4. 엠포디오

5. 농부

6. 피디아스


1. 아르테미스

제우스는 황무지의 여신인 아르테미스에게, 숲을 조성하라고 직사각형 모양의 땅을 주었다. 이 직사각형의 왼쪽에 있는 수직선을 y축으로, 아래에 있는 수평선을 x축으로 잡고, 왼쪽 아래 모서리의 점을 (0, 0)인 원점이라 하자. 제우스는 아르테미스에게, 이 영역에서 정수 좌표에 해당하는 위치에만 나무를 심으라고 분부했다. 아르테미스는 숲이 자연스럽게 보이는 걸 좋아하기 때문에, 어떤 나무 두 그루도 x축이나 y축에 평행한 간격으로 있지 않게 나무들을 배치했다.

이따금씩 제우스는 아르테미스로 하여금 나무를 베어 달라고 요청하기도 한다. 나무를 베는 규칙은 다음과 같다.

  1. 최소한 T 그루 이상의 나무를 베어야 한다.
  2. 숲 안에 일정한 직사각형 구역을 정하고, 그 안이나 구역 경계에 접해 있는 나무를 모두 베어야 한다.
  3. 이 직사각형 구역은 숲의 x축과 y축에 평행하다.
  4. 직사각형의 한 꼭지점과 그것의 대각선 맞은편 꼭지점은 반드시 나무가 있는 곳이어야 한다. 따라서, 그 꼭지점에 속한 나무도 베어지게 된다.

나무를 좋아하는 아르테미스는 필요 이상의 나무를 가능한 한 베지 않으면서 위 조건을 만족하게 나무를 베고 싶어한다. 숲에 대한 정보와 베어야 하는 최소한의 나무의 수 T를 받아들여, 아르테미스가 숲에서 나무를 베어야 할 구간을 정하는 프로그램을 작성하시오.

입력 (artemis.in)

첫째 줄에는 숲에 있는 나무의 그루 수 N이 들어있다. 둘째 줄에는 베어야 하는 최소한의 나무 수인 T가 들어있다. 그리고 다음 N개의 줄에는 각 나무들의 위치가 X좌표와 Y좌표 차례로 들어있다. 모든 테스트 케이스에 대해, 1≤ N ≤ 20000, 0≤ X,Y ≤ 64000이고, 1<T≤N이다. 또한, 전체 테스트 케이스 중 절반은 1 < N < 5000이다.

3
2
1 1
2 3
5 6

출력 (artemis.out)

한 줄에 두 개의 정수 I, J를 출력한다. 아르테미스가 나무를 자르는 기준으로 삼을 직사각형 구역은 한쪽 꼭지점이 I째 나무(입력 파일에서 위치 좌표가 I+2째 줄에 나오는 것)이고, 대각선 맞은편 꼭지점은 J째 나무(J+2째 줄에 있는 나무의 위치)로 하는 것이 좋다는 뜻이다. 두 점의 순서는 어떤 것으로 해도 무방하며, 최적해가 여러 개 있더라도 한 가지 경우에 대해서만 출력하면 된다. 모든 테스트 케이스에는 조건을 만족하는 해가 하나 이상 반드시 존재한다.

1 2


2. 헤르메스의 심부름

그리스 신들이 사는 현대식 도시에는 길거리의 도로들이 X, Y 축에 평행하며 정수 좌표로 된 격자 형태로 배열되어 있다. 임의의 정수 Z에 대해, y=Z로 표현되는 수평 도로가 있고, x=Z로 표현되는 수직 도로가 있다. 그래서 정수로 구성된 좌표는 수평· 수직 도로가 만나는 교차로가 된다.

날씨가 더우면 신들은 바로 이 교차로들 중 어디엔가 있는 카페테리아에 따로 따로 흩어져 쉰다. 신들의 심부름꾼인 헤르메스는 이날도 길거리의 도로만 이용하여 이동한 뒤, 여러 카페테리아에 흩어져 있는 신들에게 메시지를 부지런히 전달한다. 한 메시지는 한 신만을 대상으로 하고 있으나, 전달 과정에서 메시지가 다른 신이 있는 지점을 통과하더라도 상관은 없다.

헤르메스는 초기에 원점 (0, 0)에 있다. 전달 순서라는 개념이 존재하기 때문에 헤르메스는 자신에게 가까운 곳부터가 아니라 먼저 소식을 전해야 하는 신에게 먼저 메시지를 전달해야 한다. 단, 메시지는 직진하는 광자를 발사하는 방식으로 전하기 때문에, 헤르메스는 목적지인 신이 있는 곳과 x 위치가 같거나 y 위치가 같은 지점까지만 가면 된다. 전해야 하는 메시지를 모두 전하면 헤르메스의 임무는 끝난다.

가야 하는 카페테리아들의 위치를 입력으로 받아, 헤르메스가 각 지점들을 순서대로 방문하며 메시지를 전달하는 데 필요한 최소한의 이동량을 계산하는 프로그램을 작성하시오.

입력 (hermes.in)

첫째 줄에는 전해야 하는 메시지의 총 개수 N이 있다. 그리고 다음 N줄에는 각 메시지를 전하기 위해 방문해야 하는 카페테리아가 교차로의 어느 위치에 있는지, 그 좌표가 한 줄에 하나씩, X, Y 축 순으로 들어있다. 모든 테스트 케이스에 대해 1≤ N ≤ 20000, -1000≤ 카페테리아의 X, Y좌표 ≤ 1000이다. 또한, 전체 테스트 케이스 중 절반은 1≤ N ≤ 80이다.

5
8 3
7 -7
8 1
-2 1
-2 1
6 -5

출력 (hermes.out)

최소의 이동 거리를 나타내는 숫자 하나를 한 줄에다 출력한다.

11

(0, 0)에서 (8, 0), (7, 0), (7, 1), (6, 1)의 순으로 이동하면, 이동량이 최소인 11이 되면서 위의 다섯 곳에 모두 순서대로 메시지를 전할 수 있다.


3. 다각형 분해

다각형은 그 경계 위에 놓인 모든 점과 그 안의 모든 영역으로 구성되어 있다. 그 중, 다각형 안의 임의의 두 점 X, Y에 대해 이들을 잇는 선분도 완전히 그 다각형 안에 속해 있는 것을 볼록다각형이라 한다. 다각형은 두 개(이 경우, 직선이 되며 직선은 다각형의 특수한 형태임) 이상의 꼭지점으로 이루어져 있으며 세 꼭지점이 한 직선 위에 있는 경우는 없다. 이 문제에서 다루는 다각형은 모두 이러한 특성들을 만족하는 것만을 대상으로 하며, 앞으로 '다각형'이라고만 해도 그런 것들을 일컫기로 하겠다.

두 다각형 A, B가 있을 때, 이들의 민코프스키 합은, A의 임의의 꼭지점 좌표 (x1, y1)와 B의 임의의 꼭지점 좌표 (x2, y2)에 대해, 있을 수 있는 모든 (x1+x2, y1+y2) 조합을 꼭지점으로 갖는 도형이다. 다각형 A, B의 민코프스키 합 역시 다각형임을 알 수 있다. 다음은 두 삼각형과 이들의 민코프스키 합을 그림으로 나타낸 것이다.

우리는 민코프스키 합으로 합성된 다각형을, 원래의 두 다각형으로 복원하려고 한다. 좀더 구체적으로 말하면, 어떤 다각형 P가 있을 때 우리가 찾는 것은 두 다각형 A, B로, 이들은 다음과 같은 조건을 만족해야 한다.

A나 B가 P 그 자체일 수는 없음을 두말할 나위가 없을 것이다. A, B 중 하나가 원래의 도형이면 다른 하나는 (0, 0)에 있는 점이 되어 버리고, 이것은 다각형이 아니기 때문이다.

이 문제에서는 다각형 P가 어떤 모양인지를 기술한 여러 입력 파일이 주어진다. 각 입력에 대해 위의 조건을 만족하는 원래 다각형 A, B를 구한 뒤, 이들이 어떤 모양인지를 출력 파일로 만들어 제출하시오. 각 입력들은 A와 B가 반드시 존재하는 경우들이며, 조건을 만족하는 풀이가 여러 개 존재하더라도 하나만 선택하면 된다. 이번 문제는 출력 파일을 만드는 프로그램이 아니라 출력 파일 자체만 제출하도록 한다.

입력

polygon1.in부터 polygon10.in까지 열 개의 다각형 예제를 받는다. 파일 이름 뒤의 번호가 테스트 케이스의 번호이다. 각 파일의 첫 줄에는 다각형 P의 꼭지점 개수인 N이 들어있고, 다음 N줄에는 다각형 꼭지점들의 좌표가 반시계 방향으로 한 줄에 한 꼭지점씩 순서대로 들어있다. 각 줄에서 좌표는 X축, Y축의 순으로 있고, 숫자 사이는 공백 한 칸으로 구분돼 있다. 모든 좌표는 음이 아닌 정수이다.

polygon0.in
5
0 1
0 0
2 0
2 1
1 2

출력

각 10개의 입력에 대한 다각형 A, B를 구한 출력 파일을 10개 제출한다. 출력 파일 이름에 대한 특별한 규정은 없으며, 단지 출력 파일의 형식만 다음과 같이 맞추면 된다. 그 구조는 입력 파일의 형식과 유사하다.

첫 줄에는 "#FILE polygon I" (1≤ I ≤10)을 기록한다. I는 이 출력 파일과 대응하는 입력 문제의 번호이다. 둘째 줄에는 다각형 A의 꼭지점 개수를 기록하고(2≤ NA ≤4), 다음 NA 줄에는 다각형 A의 꼭지점을 반시계 방향으로 입력 파일과 같은 형식으로, 차례대로 기록한다.

NA+3째 줄에는 다각형 B의 꼭지점 개수인 NB를 기록한다(2 ≤ NB). 그리고 다음 NB개의 줄에는 다각형 B의 꼭지점 좌표를 반시계 방향으로 차례대로 기록한다. 위의 입력에 대해,

#FILE polygon 0
3
0 0
2 0
1 1
2
0 1
0 0

#FILE polygon 0
3
0 0
2 0
1 1
3
0 1
0 0
1 0

는 모두 맞는 풀이이다. 다각형 A가, 이 입력에 대해 가장 많은 변을 가질 수 있는 형태인 삼각형이라는 점에서 같기 때문이다. (사변형일 수는 없음)


4. 엠포디오

고대의 수학자· 철학자인 피타고라스는, 실존하는 것의 본질은 수학이라고 믿었다. 그 후, 오늘날의 생물학자들은 생물학적 수열이라는 것을 연구하고 있는데, 이것은 M개의 정수로 되어 있으면서 그 짜임이 다음 조건을 만족하는 수열이다.

수열 안에서 둘 이상의 인접해 있는 일부 원소를 뽑은 것을 구간이라고 하자. 생물학적 수열 안에 어떤 구간이 있는데, 첫째, 구간의 맨 앞에 있는 수가 그 구간 전체의 수들 중에 가장 작고, 둘째, 구간 맨 뒤에 있는 수가 구간 전체에서 가장 큰 수이며, 셋째, 그 구간 안에 최소값(처음)과 최대값(끝) 사이의 모든 수가 들어있으면 그 구간은 "갖춘 구간"이라고 한다. 여기에 덧붙여, 그 구간 안에 더 짧은 갖춘 구간이 존재하지 않으면 그 갖춘 구간을 엠포디오라고 일컫는다.

예를 들어, (0, 3, 5, 4, 6, 2, 1, 7)이라는 생물학적 수열이 있다고 하자. 생물학적 수열의 정의는 갖춘 구간의 조건을 포함하고 있기 때문에 이 수열 전체가 갖춘 구간이라 할 수 있다. 그러나 이 안에는 더 짧은 갖춘 구간인 (3, 5, 4, 6)이 있으므로 수열 전체를 엠포디오라고 할 수는 없다. 갖춘 구간 (3, 5, 4, 6) 안에는 다른 갖춘 구간이 더 없으므로 이것은 엠포디오이다. 또한, 이 구간이 그 수열 전체에서 유일한 엠포디오이다.

생물학적 수열을 입력받아 이 안에 존재하는 엠포디오 구간을 모두 찾는 프로그램을 작성하시오.

입력 (empodia.in)

첫 줄에는 생물학적 수열의 길이를 나타내는 정수 M이 들어있다. 다음 M개의 줄에는 수열을 구성하는 정수가 하나씩 순서대로 들어있다. 스무 개의 테스트 케이스 중 하나는 100만≤ M ≤110만이다. 다른 모든 테스트 케이스는 1≤ M ≤ 60000이나, 전체의 절반(10개)은 M ≤ 2600이다. 참고로, empodia는 엠포디오(empodio)의 복수형을 표기한 것이다.

8
0
3
5
4
6
2
1
7

출력 (empodia.out)

첫 줄에는 이 생물학적 수열에 존재하는 엠포디오의 개수 H를 출력한 뒤, 다음 H줄에는 엠포디오의 위치를 작은 순서에서 큰 순서로 차례대로 출력한다. 각 줄에는 두 정수 A와 B를 공백 하나로 구분하여 출력하는데, A는 각 줄에 해당하는 엠포디오의 첫 원소의 번호(1부터 시작)이고, B는 마지막 원소의 번호이다.

1
2 5

(둘째 원소인 3과, 다섯째 원소인 6을 의미)


5. 농부

여러 개의 정원과 여러 개의 이랑--일렬로 나무나 곡식을 심는 길쭉한 길--을 소유한 한 농부가 있다. 정원의 경계는 사이프러스 나무로 둘러싸여 있으며, 각 이랑에도 사이프러스 나무가 심어져 있다. 또한 정원과 이랑 모두, 두 사이프러스 나무 사이에는 올리브 나무가 한 그루 심어져 있다. 이런 식으로 농부의 모든 사이프러스 나무는 정원을 둘러싸거나 이랑을 따라 심어져 있으며, 사이프러스 나무 두 그루 사이에는 반드시 올리브 나무가 한 그루 끼여 있다.

그러던 어느날, 농부는 심한 병에 걸려 임종을 앞두게 되었다. 숨을 거두기 며칠 전, 그는 맏아들에게 이렇게 말했다. "내 정원과 이랑에 심어진 사이프러스 나무들을 아무 거나 Q 그루 골라라. 그러면 그 나무들과, 두 나무 사이에 심겨져 있는 올리브 나무까지 모두 네게 주겠다."

아버지의 유언에 따라 아들은 정원 경계나 이랑에서 연속하는 구간을 하나 이상 선택하여 사이프러스 나무를 최대 Q 그루까지 얻을 수 있고, 그 사이에 있는 올리브 나무들도 얻을 수 있다. 아들은 올리브를 매우 좋아하기 때문에 올리브 나무를 가장 많이 얻을 수 있는 구간을 선택하고 싶어한다.

농부에게 정원과 이랑이 세 개씩 있고, 사이프러스 나무가 각 곳에 위의 그림과 같이 있다고 가정하자. (사이프러스 나무 사이에 있는 올리브 나무는 편의상 표기하지 않았다) 그리고 Q=17그루의 사이프러스 나무를 물려받을 수 있다고 하자. 그렇다면 아들은 정원 1과 2에 있는 사이프러스 나무만을 모두 선택하면 된다. 정원은 이랑과는 달리 고리를 이루고 있기 때문에, 그 안에 있는 17그루의 올리브 나무를 모두 물려받을 수 있기 때문이다.

밭과 이랑에 있는 나무 수와 물려받을 수 있는 나무의 수를 입력으로 받아, 아들이 물려받을 수 있는 올리브 나무의 최대 수를 구하는 프로그램을 작성하시오.

입력 (farmer.in)

첫째 줄에는 아들이 물려받을 수 있는 나무의 그루 수 Q와, 정원의 수 M, 그리고 이랑의 수 K가 들어있다. 둘째 줄에는 각 정원에 있는 사이프러스 나무의 수가 M개 있으며(N1~Nm), 다음 줄에는 각 이랑에 있는 사이프러스 나무의 수가 K개 있다(R1~Rk).

0≤ Q ≤15만, 0≤ M, K ≤2000이고, 한 정원이나 이랑에 있는 나무의 수는 2 이상 150 이하이다. 모든 정원과 이랑에 있는 나무들의 총합은 반드시 Q보다 같거나 크다. 또한 전체 테스트 케이스의 절반은 Q≤1500이다.

17 3 3
13 4 8
4 8 6

출력 (farmer.out)

아들이 덤으로 받을 수 있는 올리브 나무의 최대 그루 수를 출력한다.

17


6. 피디아스

고대 그리스의 유명한 조각가인 피디아스는 또다른 걸작을 만들기 위한 준비 작업을 하고 있다. 그래서 가로 세로 크기가 W1×H1, W2×H2, ... Wn×Hn인 직사각형 모양의 대리석 돌판이 여러 장 필요한 상태이다.

얼마 전, 피디아스는 커다란 직사각형 돌판을 받았다. 그래서 이것을 원하는 크기에 해당하는 돌판들로 쪼개고 싶어한다. 돌판은 임의의 정수 위치에서 가로나 세로로 완전히 잘라서 두 개의 직사각형 모양으로 자를 수 있다. 하지만 작은 돌판들을 붙여서 큰 판으로 만들 수는 없다. 또한, 돌판에는 일정한 방향으로 무늬가 있기 때문에, 회전해서 원하는 크기를 만들 수는 없다. 다시 말해, A×B라는 크기로 잘랐다면 이것을 B×A라는 크기에 맞추어 사용할 수는 없다는 뜻이다. 돌판에서 원하는 크기에 해당하는 면을 모두 잘라 낸 뒤, 어느 크기로도 쪼갤 수 없어 남게 된 면들은 버려진다. 피디아스는 원판을 어떻게 자르면 이러한 손실을 가능한 한 줄일 수 있을지 알고 싶어한다.

가로 길이가 21이고 세로 길이가 11인 커다란 돌판을 예로 들어 보자. 그리고 우리에게 필요한 돌판 크기의 종류가 10×4, 6×2, 7×5, 그리고 15×10이라고 가정하자. 이 경우 돌판을 아래 그림과 같이 자르면, 각 크기에 해당하는 돌판을 각각 두 장, 세 장, 세 장씩 얻으면서 손실되는 영역의 넓이는 10으로 가장 작게 된다.

15×10의 크기는 한 장이라도 넣을 경우 전체의 손실이 너무 커지기 때문에, 만들기를 포기한 것이다. 한편으로, 가장 넓이가 작은 돌판만으로 여러 장을 잘라 낸다고 해도 손실을 이보다 줄일 수 없다는 것은, 손으로 따져 보면 금방 알 수 있다.

돌판의 원래 크기와 우리가 원하는 돌판 크기들을 입력 받은 뒤, 가장 효율적으로 돌판을 자르는 방법을 계산하여 그때 손실되는 최소한의 돌판 면적의 합을 구하는 프로그램을 작성하시오. 어느 크기의 돌판을 얼마나 얻느냐가 아니라, 어떻게 자르든 손실을 줄이는 것이 목적이다.

입력 (phidias.in)

첫 줄에는 대리석 원판의 크기를 나타내는 W(가로 길이), H(세로 길이)가 들어있다. 다음 줄에는 우리가 원하는 크기의 개수 N이 있고, 그다음 N줄에는 그 크기들이 역시 가로, 세로 순으로 들어있다. 1≤ W, H ≤600이고 0 < N ≤ 200이다. 잘라야 하는 크기는 가로· 세로 모두 1 이상이고 원판의 크기 이하이다. 단, 전체 테스트 케이스 중 절반은 W, H ≤20이고 N≤5이다.

21 11
4
10 4
6 2
7 5
15 10

출력 (phidias.out)

정수 하나를 출력한다. 원판을 가장 현명하게 잘랐을 때 손실되는 면적의 최소값이다.

10