제 20회

제 20회는 2008년 8월 16일부터 23일까지 이집트 카이로에서 열렸다. 거의 10년만에 대화형, 제출형 문제가 전혀 출제되지 않고 모두 전통적인 일괄 처리 문제만 나왔다. 정작 practice competition(day 0이라고, 대회 환경과 채점 시스템에 적응하기 위해 아주 쉬운 문제를 출제하고 실제 성적에는 반영하지 않는 몸풀기 시험)에는 대화형, 제출형 문제가 있었는데 뜻밖이다. 이집트에서 열린 대회답게 피라미드를 소재로 한 문제가 어김없이 출제되었는데, 사실 비슷한 소재가 멕시코 대회 때도 출제된 적이 있다.

나머지 다섯 문제들은 역시 숫자 하나만 출력하는 형태인 반면, 1번만 구체적인 문제 풀이 과정을 모두 출력할 것을 요구하는 형태이다.

3번과 4번은 모두 조합론과 관련된 문제이다. 특히 4번은 2001년도 3번 스물다섯자 언어 문제와 함께 보면 흥미로울 것 같다. 64비트 출력를 요구하는 문제는 2번 하나뿐인 반면, 이 조합론 문제들은 그냥 숫자를 출력하는 게 아니라 답을 지정된 숫자 M으로 나눈 나머지로 출력하게 하는 것이 특이하다.

600점 만점에 금메달 입상자의 최고 점수는 중국 학생이 획득한 558점인데, 2등인 474점보다 월등한 격차로 앞선 점수였다. 그리고 동메달 입상자의 최저 점수는 127점이었다. 이번 대회에서 우리나라는 금메달 1개, 은메달 3개를 획득했다.

원문이 있는 곳: http://www.ioi2008.org/index.php

1. 가변 활자 인쇄기

2. 섬 순회

3. 물고기 뱃속의 보석

4. 일렬로 꾸미기

5. 순간이동 장치

6. 피라미드 부지

1. 가변 활자 인쇄기

이번 문제의 목표는 가변 활자 인쇄기로 N개의 단어를 출력하는 것이다. 가변 활자 인쇄기란, 인쇄를 원하는 글자가 찍힌 작은 금속 활자들을 마음대로 끼웠다 빼면서 쓰던 과거의 재래식 인쇄기를 말한다. 사람이 넣어 준 활자들이 종이에 한꺼번에 찍힘으로써 단어가 완성된다. 이 인쇄기에다 취할 수 있는 동작은 아래와 같다.

처음에는 인쇄기에 아무 활자도 들어있지 않다. 원하는 단어를 모두 인쇄한 직후에 인쇄기의 활자 배열이 어떤 상태가 되어 있든지 상관 없다. 또한 지정된 단어들을 어떤 순서로 출력하든 그것도 상관 없다.

활자를 넣고 빼는 것은 시간이 소요되는 작업이다. N개의 단어를 입력 받아서 이 단어들을 모두 출력하는 데 필요한 최소한의 동작 횟수를 계산하고, 그 실제 동작 과정을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 출력하려는 단어의 개수 N이 들어있다. (1≤N≤25,000)

다음 N개의 줄에는 단어가 하나씩 들어있다. 단어는 소문자 a~z로만 구성되어 있으며 길이는 1자 이상 20자 이하이다. 모든 단어들은 중복이 없이 서로 다 다르다.

3
print
the
poem

출력

첫째 줄에는 이 N개의 단어를 모두 출력하는 데 필요한 최소 동작 횟수 M을 출력한다. 다음 M개의 줄에는 각 줄마다 동작을 기술하는 한 글자를 출력한다. (메모리 제한: 64MB, 시간 제한: 1초)

20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P

테스트 케이스 중 전체의 40점에 해당하는 케이스는 N의 값이 18을 초과하지 않는다.

2. 섬 순회

당신은 N개의 섬으로 구성된 한 공원을 방문하고 있다. 모든 섬에는 어느 섬으로든 이어진 다리가 정확하게 하나씩 있다. i째 섬에서 외부로 나가는 다리의 길이를 Li라고 하자. 따라서 공원에는 N개의 다리가 존재하는 셈이다. 물론 다리는 양방향으로 모두 통행 가능하다. 그에 덧붙여 페리도 왕복 운행을 하고 있기 때문에 아무 섬에서 아무 섬으로나 원하는 대로 이용할 수 있다.

하지만 당신은 페리를 타는 것보다 걷는 것을 더 좋아한다. 그렇기 때문에 공원을 순회하면서 다리를 따라 걷는 거리를 최대화하되, 아래의 조건을 만족하고 싶어한다.

모든 섬들을 하나도 빠짐없이 들러야 할 필요는 없다. 또한 공원에 존재하는 다리를 전부 거치는 것이 불가능할 수도 있다.

N개의 다리의 위상 정보와 길이를 입력 받아, 위의 규칙대로 공원을 순회하면서 다리들을 이용해 걸을 수 있는 가장 긴 거리를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 공원에 있는 섬의 수 N이 들어있다. 섬들은 1 이상 N 이하 범위인 번호로 식별한다. (2≤N≤1,000,000)

다음 N 줄에는 다리에 대한 정보가 있다. i째 줄에는 i째 섬에 달려 있는 다리가 연결하는 다른 섬의 번호와 이 다리의 길이 Li가 순서대로 공백 사이에 들어있다. 자기 자신을 가리키는 다리는 없으며 다리의 시작점과 끝점은 항상 서로 다르다. (1≤Li≤100,000,000)

7
3 8
7 2
4 2
1 4
1 9
3 4
2 3

출력

걸을 수 있는 최장거리를 나타내는 정수 하나를 출력하면 된다. (메모리 제한: 128MB, 시간 제한: 2초)

테스트 케이스 중 일부는 출력하는 답이 32비트 정수의 범위를 벗어날 수도 있으므로 파스칼의 경우 int64를, C/C++에서는 long long 형을 사용하기 바란다.

한편, 파스칼은 데이터를 64비트로 읽어들이는 속도가 32비트보다 대단히 느리다. 이는 실제로 들어있는 값이 32비트 범위에 들더라도 마찬가지이기 때문에, 입력 파일을 읽어들일 때에는 언제나 32비트 자료형을 사용하기 바란다.

24

예제로 제시되어 있는 N=7 공원은 (1-3), (2-7), (3-4), (4-1), (5-1), (6-3), (7-2)와 같은 형태로 섬들이 다리로 연결되어 있다. 2번 섬과 7번 섬은 다리가 두 개 존재함을 주목하기 바란다.

도보 경로를 가장 길게 확보하려면 섬을 다음과 같이 순회하면 된다.

순회는 2번 섬에서 끝나며 이때 당신이 걸은 총 거리는 9+8+4+3=24이다.

한 번도 들르지 않은 유일한 섬은 4번 섬이다. 하지만 이제는 거기에 갈 수 없다. 왜냐 하면 2번 섬과 4번 섬은 직통으로 연결하는 다리가 없이 고립되어 있어서 일단 도보로 갈 수 없으며, 위의 규칙대로라면 페리도 이용할 수 없기 때문이다. 이미 페리를 이용한 구간인 (6-7)까지 감안하면 2번 섬과 4번 섬은 이제 연결된 것으로 간주되기 때문이다. (다리 2-7, 이미 이용한 페리 7-6, 다리 6-3, 다리 3-4로 연결) 페리는 그런 방법으로 도달할 수 없는 완전히 새로운 곳으로만 이용할 수 있다.

테스트 케이스 중 전체의 40점에 해당하는 케이스는 N의 값이 4,000을 초과하지 않는다.

3. 물고기 뱃속의 보석

아라비안 나이트를 들려 준 셰에라자드 왕비의 이야기에 따르면, 어떤 사막의 한복판엔 호수가 하나 있었다고 한다. 원래 이 호수에는 F 마리의 물고기가 살았다. 그리고 이 땅에서 가장 귀중한 보석들이 K 종류 선정되어 모든 물고기들이 이 보석을 한 덩이씩 삼켰다. K의 값은 F보다 작을 수 있기 때문에 동일한 종류의 보석을 두 마리 이상의 물고기가 먹었을 수도 있다.

시간이 흐르면서 어떤 물고기는 다른 물고기를 잡아먹기도 했다. 물고기는 몸길이가 자신의 절반 이하인 것만 잡아먹을 수 있다. (물고기 A가 물고기 B를 잡아먹기 위해서는 LA ≥ 2×LB여야만 한다.) 물고기가 언제 다른 물고기를 잡아먹는지에 대해서는 특별한 규칙이 없다. 어떤 물고기는 자기보다 충분히 작은 물고기들을 수 차례 잡아먹었을 수 있으나, 어떤 물고기는 다른 물고기를 잡아먹을 수 있는데도 그렇게 하지 않았을 수도 있다. 다른 물고기를 잡아먹은 물고기는 몸길이는 변하지 않으나, 잡아먹힌 물고기의 뱃속에 있던 보석을 자기 뱃속에 고스란히 갖고 있게 된다.

모든 물고기에 보석이 들어있는 이 호수를 찾아낼 수만 있다면 당신은 믈고기를 잡아 뱃속의 모든 보석을 차지할 수 있다고 셰에라자드 왕비는 말했다. 이제 당신의 운을 시험할 때가 온 것이다. 하지만 호수를 찾아 긴 여행을 떠나기에 앞서, 당신은 물고기를 하나 잡았을 때 얻을 수 있는 보석들의 조합 가짓수가 얼마나 존재할지 알고 싶어한다.

물고기들의 몸길이와 초창기에 이들이 하나씩 삼킨 보석들의 종류 수를 입력 받아, 물고기를 아무 거나 하나 잡았을 때 이 물고기의 뱃속에 있을 수 있는 보석의 조합 가짓수를 찾아서 이 값을 어떤 정수 M으로 나눈 나머지를 출력하는 프로그램을 작성하시오. 한 조합이란 K개의 종류별 보석 개수만으로 구성된다. 보석을 얻은 순서라든가, 종류가 같은 두 보석끼리는 구분을 하지 않는다.

이 M이라는 수는 문제 풀이를 더 쉽게 해 주기 위해 있는 것으로, 다른 의미는 없음을 밝힌다.

입력

첫째 줄에는 최초에 호수에 들어있던 물고기의 개체수 F가 들어있다. (1≤F≤500,000)

둘째 줄에는 보석의 종류 수 K가 들어있다. (1≤K≤F) 보석의 종류를 식별하는 번호는 1 이상 K 이하의 범위에 드는 정수이다.

셋째 줄에는 정수 M이 있다. (2≤M≤30,000)

다음 F개의 줄에는 각 물고기의 몸길이와 자신이 초기에 삼킨 보석의 종류 번호가 공백을 사이에 두고 들어있다. (1≤Lx≤1,000,000,000) 모든 종류의 보석이 최소한 한 물고기 이상의 뱃속에는 들어있으며, 1부터 K 중 존재하지 않는 보석은 없다고 가정해도 된다.

5
3
7
2 2
5 1
8 3
4 1
2 3

출력

0 이상 M-1 이하의 범위에 있는 정수 하나를 출력한다. 보석들의 모든 조합 가짓수를 M으로 나눈 나머지의 값이다. (메모리 제한: 64MB, 시간 제한: 3초)

4

위의 입력에 대한 가능한 조합 가짓수는 11이기 때문에, 이를 7로 나눈 나머지인 4를 출력하면 된다. 그 조합을 나열하면 다음과 같다. [1] [1,2] [1,2,3] [1,2,3,3] [1,3] [1,3,3] [2] [2,3] [2,3,3] [3] [3,3] (각 숫자 하나가 물고기 배에 있는 보석을 뜻한다. 가령 [2,3,3]은 2번 보석 하나와 3번 보석 두 개를 가리킴.)

테스트 케이스 중 전체의 70점에 해당하는 케이스는 K의 값이 7,000을 초과하지 않는다. 또한 이들 중에 전체의 25점에 해당하는 케이스는 K의 값이 20을 초과하지 않는다.

4. 일렬로 꾸미기

람세스 2세가 전투에서 승리를 거두고 귀환했다. 그는 승리를 기리기 위해 웅장한 정원을 조성하기로 결심했다. 그래서 궁궐이 있는 Luxor에서부터 시작해 Karnak 신전에 이르는 긴 길을 따라 식물을 일렬로 쭉 심을 예정이다. 심는 식물은 연꽃(L)과 파피루스(P) 이렇게 단 두 종류이다. 이들은 각각 이집트 북부와 남부의 상징이기 때문이다.

정원에는 그런 식으로 N개의 식물을 심는데, 종류별 식물 배치에 균형이 있어야 한다. 정원 내부의 어느 구간(연속적인)이라도 양 종류의 식물의 개수 차이가 2를 넘어서는 안 된다.

람세스가 세우고자 하는 정원은 L 아니면 P로 이루어진 문자열로 나타낼 수 있다. 예를 들어 N=5인 경우 위에서 제시한 균형을 갖춘 정원은 14가지가 있을 수 있다. (LLPLP, LLPPL, LPLLP, LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP, PPLPL)

그리고 특정 길이에 대해 균형을 갖춘 정원 식물 배치를 나타내는 문자열들은 알파벳 오름차순으로 나열하여 1부터 번호를 매길 수 있다. 가령 N=5의 경우, 12번에 해당하는 정원 문자열은 PLPPL이다.

길이가 N인 균형 잡힌 정원을 나타내는 어떤 문자열을 입력 받아 이것이 그 길이에 해당하는 전체 균형 잡힌 정원 문자열 중 오름차순으로 몇째 순서에 해당하는지 서열을 구하고, 이 값을 어떤 정수 M으로 나눈 나머지를 출력하는 프로그램을 작성하시오. 단, 이 M이라는 수는 문제 풀이를 더 쉽게 해 주기 위해 있는 것으로, 다른 의미는 없음을 밝힌다.

입력

첫째 줄에는 정원에 일렬로 심을 식물의 수 N이 있다. (1≤N≤1,000,000) 둘째 줄에는 정수 M이 있다. (7≤M≤10,000,000)

셋째 줄에는 균형 잡힌 정원을 나타내는 문자열이 있다. 길이가 N이며 모든 문자는 L(연꽃) 아니면 P(파피루스)로만 구성되어 있다.

#1 #2
5
7
PLPPL		 12
10000
LPLLPLPPLPLL

출력

0 이상 M-1 이하의 범위에 있는 정수 하나를 출력한다. 입력 파일에 들어있는 정원 문자열의 오름차순 서열을 M으로 나눈 나머지의 값이다. (메모리 제한: 64MB, 시간 제한: 1.5초)

#1 #2
5 39

PLPPL의 실제 서열은 12인데, 이를 7로 나눈 나머지인 5를 출력한 것이다.

테스트 케이스 중 전체의 40점에 해당하는 케이스는 N의 값이 40을 초과하지 않는다.

5. 순간이동 장치

당신은 이집트를 서쪽에서 동쪽으로 직선으로 횡단하는 어느 경기에 참가하고 있다. 초기에 경기는 서쪽 끝에서 시작하며, 규정상 언제나 길을 따라 동쪽으로만 이동해야 한다.

그런데 길에는 곳곳에 N개의 순간이동 장치가 설치돼 있다. 순간이동 장치는 두 지점이 한 쌍으로 존재하여 한 지점에 도달한 사람을 다른 지점으로 즉시 옮겨 놓는다. (스타크래프트의 Nydus Canal과 같은 개념) 그래서 순간이동 장치에 도달한 사람은 어느 쪽 지점에 닿았냐에 따라 지금보다 동쪽으로 갈 수도 있고, 왔던 길인 서쪽으로 되돌아갈 수도 있다.

순간이동 된 후에도 당신은 계속해서 동쪽으로 가던 길을 가야 한다. 또한 순간이동 장치가 있는 지점을 순간이동 없이 그냥 무시하고 통과할 수도 없다. 당연한 가정이지만 순간이동 장치가 두 지점이 동일 위치에 겹치는 경우는 없으며, 두 지점은 모두 경기 코스 내부에만 존재한다.

순간이동을 한 번 할 때마다 당신은 1점을 얻는다. 이 경기의 목표는 점수를 최대한 많이 따서 횡단을 마치는 것이다. 점수를 많이 따기 위해, 당신은 경기를 시작하기 전에 최대 M개의 순간이동 장치를 추가로 요구할 수 있다. 추가된 순간이동 장치로 순간이동을 해도 물론 점수를 얻는다.

새 순간이동 장치의 양 지점은 기존 순간이동 장치들의 지점과 겹치지만 않는다면 아무 곳에나, 심지어 정수가 아닌 위치에도 설정할 수 있다. 모든 순간이동 장치들의 지점 위치는 제각기 달라야 하며 새 순간이동 장치들도 지점의 위치가 반드시 경기 코스 내부에 존재해야 한다. 참고로, 이 규정대로라면 순간이동 장치를 어떤 방식으로 설치하더라도 무한 순환에 빠지는 일이 없이 동쪽까지 경기 완주는 언제나 가능하다는 사실을 염두에 두기 바란다.

N개의 기본 순간이동 장치들의 위치와 당신이 추가 가능한 순간이동 장치 개수의 최대치 M을 입력 받아서, 이 경기 코스에서 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 처음에 경기 코스에 놓여 있는 순간이동 장치의 개수 N이 들어있다. (1≤N≤1,000,000)

둘째 줄에는 당신이 추가 설치 가능한 순간이동 장치의 최대 개수 M이 들어있다. (1≤M≤1,000,000)

다음 N개의 줄에는 각 순간 이동 장치의 양 지점 위치가 순서대로 들어있다. 서쪽 출발점의 좌표가 0이고 동쪽 종점은 2,000,001이라고 했을 때, 순간이동 장치의 서쪽 지점과 동쪽 지점의 좌표 Wi, Ei가 공백 사이에 들어있는 형태이다. (1≤Wi<Ei≤2,000,000)

#1 #2
3
1
10 11
1 4
2 3		 3
3
5 7
6 10
1999999 2000000

출력

이 경기에서 득점 가능한 최대 점수를 정수 하나로 출력하면 된다. (메모리 제한: 64MB, 시간 제한: 1초)

#1 #2
6 12

테스트 케이스 #1의 예를 보면,  0.5와 1.5 지점을 순간이동 장치로 연결하면 된다. 이렇게 하고 경기를 시작하면, 당신은 0~0.5 (1점) → 1.5~2 (2점) → 3~4 (3점) → 1~1.5 (4점) → 1.5~1 (5점) → 4~10 (6점)의 순으로 여섯 번 순간이동을 하며 그 뒤로는 순간이동 장치를 더 만나는 일이 없이 종점에 도달한다. 따라서 총 6점을 얻는다.

테스트 케이스 중 전체의 30점에 해당하는 케이스는 N≤500이고 M≤500이다.

6. 피라미드 부지

당신은 피라미드를 새로 짓기에 적합한 가장 넓은 부지를 찾아 달라는 요청을 받았다. 작업 수행을 위해 먼저 땅 전체를 M×N 크기의 정사각형 격자로 나누어 측량해 두었다. 피라미드를 짓는 영역은 이 격자에 평행한 정사각형 형태여야 한다.

조사한 바에 따르면 이 땅에는 P개의 장애물이 존재하는데, 이들은 격자에 평행한 직사각형 형태이며 일부 영역이 다른 장애물과 겹칠 수도 있다. 피라미드를 지으려면 피라미드가 차지하는 모든 칸에 장애물이 하나도 없어야 한다. i째 장애물을 제거하는 데 드는 비용은 Ci로 표현된다. 한 장애물은 이 비용을 모두 들여서 완전히 제거하는 것만 가능하며 장애물의 일부 영역만을 부분적으로 제거할 수는 없다. 또한 한 장애물을 제거하더라도 그 장애물과 겹치는 영역이 존재하는 다른 장애물은 영향을 받지 않는다.

땅의 크기인 M과 N, P개의 장애물들의 위치와 이들 각각의 제거 비용, 내게 있는 자금 B를 입력 받아서 이 땅에서 이 자금 한도로 만들 수 있는 피라미드의 가장 큰 크기를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 M과 N의 값이 공백을 사이에 두고 들어있다. (1≤M, N≤1,000,000)

둘째 줄에는 장애물 제거를 위해 쓸 수 있는 자금 B가 들어있다. 그리고 셋째 줄에는 이 땅에 존재하는 장애물의 개수 P가 들어있다.

다음 P개의 줄에는 각 장애물에 대한 정보가 들어있다. Xi1, Yi1, Xi2, Yi2, Ci가 차례대로 공백으로 구분되어 있는데, 각각 장애물을 구성하는 직사각형의 좌측 하단 좌표와 우측 상단 좌표이며 끝으로 이 장애물의 제거 비용이 있다. 최좌측 최하단 좌표는 (1, 1)이며 최우측 최상단 좌표는 (M, N)이다. (1≤Xi1 ≤ Xi2≤M, 1≤Yi1 ≤ Yi2≤N이며 1≤Ci≤7,000)

테스트 케이스 중 전체의 35점에 해당하는 첫 그룹은 B=0이며, 1≤P≤1,000이다. 즉, 장애물의 개수는 1000개 이내이며 자금이 전혀 없기 때문에 장애물을 제거하는 경우는 고려할 필요가 없다는 뜻이다.

테스트 케이스 중 또다른 35점에 해당하는 둘째 그룹은 0<B≤2,000,000,000이며 1≤P≤30,000이다.

테스트 케이스 중 나머지 30점에 해당하는 마지막 그룹은 다시 B=0이며 1≤P≤400,000이다.

#1 #2
6 9
42
5
4 1 6 3 12
3 6 5 6 9
1 3 3 8 24
3 8 6 9 21
5 1 6 2 20		 13 5
0
8
8 4 10 4 1
4 3 4 4 1
10 2 12 2 2
8 2 8 4 3
2 4 6 4 5
10 3 10 4 8
12 3 12 4 13
2 2 4 2 21

출력

이 환경에서 지을 수 있는 피라미드의 최대 크기를 나타내는 정수 하나를 출력한다. 피라미드를 전혀 지을 수 없다면 0을 출력한다. (메모리 제한: 256MB, 시간 제한: 5초)

#1 #2
4 3

테스트 케이스 #1의 경우, 그림과 같이 길이가 최대 4인 피라미드를 지을 공간이 두 곳 존재한다. 테스트 케이스 #2는 길이가 최대 3인 피라미드를 지을 공간이 딱 하나 존재함을 알 수 있다.