제 13회

제 13회는 2001년 7월 14일부터 21일까지 핀란드 탐페레에서 열렸다. 이번 대회 개요와 문제를 보고 나는 놀라움을 금치 못했다. IOI에서 최초로 32비트 컴파일러를 채용하고, 그에 따라 프로그램의 시간/메모리 제한 규정 역시 크게 바뀐 것이다. 리눅스 종주국인 만큼 언어도 전통적으로 사용돼 오던 볼랜드 16비트 도스 언어에서 탈피, 프리파스칼과 GNU C/C++을 수험 언어로 쓰게 했으며, 수험자는 운영체제로 윈도우즈와 리눅스를 선택해서 사용할 수 있었다.

in 파일을 받아서 out 파일을 출력하는 전통적인 문제는 두 문제뿐이었다. 97년 대회를 많이 떠올리게 한다. 인터렉티브 문제가 두 개가 나온 것도 그렇고, 6번 문제의 배경도 97년 대회 6번과 유사하다. 아주 쉽고 간단한 문제에서부터 암호를 풀어 제출하는 문제까지... 이게 IOI의 새로운 경향은 아닌지 생각해 본다. 문제의 항목 사이에 일관성이 별로 없다.

총점 600점 만점에 금메달 입상자의 최고 점수는 580점, 동메달 입상자의 최저 점수는 143점이었다.

원문이 있는 곳: http://olympiads.win.tue.nl/ioi/ioi2001/contest/index.html

1. 이동 전화 (대화형)

2. IOI와리 게임 (대화형)

3. 스물다섯자 언어

4. 스코어 게임 (대화형)

5. 이중 암호화 (제출형)

6. 컨테이너 보관

※ 인터렉티브 문제(1, 2, 4번) 채점 때 실행되는 평가 프로그램은 여러분의 답안 프로그램과는 독립된 프로세스로 돌아가며, 평가 프로그램이 쓴 시간은 답안 프로그램이 쓴 시간에 포함되지 않는다.

1. 이동 전화

탐페레 시의 4세대 이동 전화 기지국은 이런 식으로 운영된다. 기지국이 있는 영역들은 정사각형 칸으로 구분된다. 정사각형들은 S*S 크기의 행렬을 이루며, 칸의 가로 세로 위치는 0부터 S-1까지 번호가 매겨져 있다. 각 영역 안에서 볼 때, 개통중인 이동 전화의 개수는 시시각각 변할 수 있다. 전화를 가진 사람이 다른 칸(영역)으로 이동할 수 있고, 전화기 전원을 켜거나 끌 수도 있기 때문이다. 그런 일이 생기면 각 기지국은 자기 영역 내에서 생긴 변화를 이동전화 본부로 보고한다.

여러 기지국에서 날아오는 보고를 받아들인 뒤, 임의의 직사각형 영역에 켜져있는 이동 전화의 총 개수를 묻는 물음에 제대로 응답해 주는 프로그램을 작성하는 게 이번 문제이다.

입출력

입력은 표준 입력 스트림으로 들어오고, 답안 프로그램은 물음에 대한 대답을 표준 출력 스트림으로 보내면 된다. 입력으로 들어오는 자료의 종류는 다음과 같다. 입력문은 한 줄로 되어 있으며, 명령 종류를 나타내는 번호와 함께 정수 몇 개가 매개변수로 들어온다.

모든 값은 항상 제한 사항을 만족하는 범위 내에 있기 때문에 그 값이 범위에 맞는지 답안 프로그램이 일일이 점검할 필요는 없다. 특히 1번 명령에서 A가 음수가 되더라도, 그 칸에서 개통중인 전화 개수가 0보다 작은 값을 갖게 되는 일은 없다. 첨자 번호는 0부터 시작한다. 따라서 구역 행렬의 크기가 4라면 X, Y의 값은 0 이상 3 이하의 값을 지니게 된다.

답안 프로그램은 2번 명령이 왔을 때 외에는 어떤 응답도 해서는 안 된다. 2번 명령이 날아오면 개통중인 전화의 합계를 계산하여 그 답을 표준 출력 스트림으로 보내면 된다.

언어별 지시 사항

2번 명령이 들어와서 여러 가지 인자를 읽어들이고 있고, last가 읽어들여야 하는 마지막 매개변수라고 하자. 그리고 answer이 출력하려고 하는 답안이라고 생각해 보자.

C++ 언어에서 iostream을 이용해서 입출력한다면 표준 스트림에 입출력하기 위해 다음과 같은 명령을 주면 된다.

cin>>last;
cout<<answer<<endl<<flush;

C/C++ 언어에서 scanf와 printf를 써서 입출력한다면 다음과 같은 명령을 주면 된다.

scanf ("%d", &last);
printf("%d\n",answer); fflush (stdout);

파스칼 언어로 입출력한다면 다음과 같은 명령을 주면 된다.

Read(last); ... Readln;
Writeln(answer);

예제

stdin      stdout     풀이

0 4                   구역 크기를 4x4로 맞춘다.
1 1 2 3               (1,2) 위치에 있는 개통 전화 수에 3을 더한다.
2 0 0 2 2             0<=X<=2, 0<=Y<=2에 해당하는 직사각형 영역에 있는 개통 전화 수의 합을 묻는다.
           3          이 물음의 대답
1 1 1 2               (1,1) 위치에 있는 개통 전화 수에 2를 더한다.
1 1 2 -1              (1,2) 위치에 있는 개통 전화 수에 1을 뺀다.
2 1 1 2 3             (1,1)-(2,3) 직사각형에 해당하는 개통 전화 수의 합을 묻는다.
           4          이 물음의 대답
3                     프로그램을 끝낸다.

제한

• 구역 행렬 크기 (S*S) : 1*1 <= S*S <= 1024*1024
• 한 순간에 칸 하나에 개통해 있을 수 있는 전화의 수 (V) : 0<=V<=32767
• 한 순간에 있을 수 있는 전화 수 변화 (A) : 0<=A<=32767

• 한 입력 파일당 있을 수 있는 명령 개수 (U) : 0<=U<=60002
• 구역 전체에 있을 수 있는 개통 전화 합계의 최대값 (M) : M=2³⁰

이 문제는 20개의 입력 데이터로 심사를 받으며, 한 데이터당 만점은 5점으로 최대 100점을 받게 된다. 그중 16개는 구역 행렬 크기가 512*512 이하이다. 한 데이터당 시간 제한은 1초이며, 메모리 제한은 5MB이다.

2. IOI와리 게임

구슬과 구멍을 두고 하는 만칼라 류의 게임은 여가 수단으로 예로부터 오랫동안 전해내려온 놀이이다. 이번 문제에서는 IOI용으로 특별히 개발된 게임을 소개하고자 한다. 이 게임은 두 명이 교대로 하며, 자기 주머니에 상대방보다 구슬을 더 많이 모으려고 한다. 게임판은 원형이며, 그 일곱 꼭지점(원에 내접한 정칠각형의 꼭지점을 생각할 것.)에는 구멍이 나 있다. 게임 초기에는 같은 종류의 구슬 20개가 일곱 구멍에 무작위로 담겨 있다. 단, 한 구멍 하나에 든 구슬 수는 최소 2개, 최대 4개가 되도록 배분된다.

게임이 시작되면, 경기자는 구슬이 하나 이상 담겨 있는 구멍을 아무거나 골라 거기 있는 구슬을 모두 꺼내서 자기 손에 쥔다. 그리고 그 구멍을 지나서 시계 방향으로 다른 구멍들을 차례대로 훑으며 다음과 같은 동작을 자기 손에 구슬이 더는 없을 때까지 행한다.

• 손에 구슬이 둘 이상 있을 때: 지금 방문하고 있는 구멍에 구슬이 이미 5개 있으면, 그 구멍에서 구슬을 하나 꺼내 구슬을 자기 주머니에 넣는다. 그렇지 않으면 손에 있던 구슬 하나를 그 구멍에 집어넣는다.
• 구슬이 하나밖에 안 남으면: 지금 방문하고 있는 구멍에 구슬이 하나 이상 넷 이하 있으면 구멍에 있는 구슬과 자기 손에 있는 유일한 구슬을 모두 자기 주머니로 옮긴다. 그렇지 않으면(구멍에 구슬이 없거나 5개 있을 때) 자기 손에 있는 구슬을 상대방 주머니로 옮긴다.

그리고 차례는 상대방에게 넘어간다. 이 과정을 반복하여 모든 구멍에 구슬이 하나도 없게 되면--구슬이 모두 두 경기자의 주머니로 옮겨지면-- 게임이 끝난다. 그리고 주머니에 구슬을 더 많이 가진 사람이 이기게 된다.

이 게임에는 필승법이 있기 때문에, 먼저 시작하는 사람은 무조건 게임에서 이길 수 있다. 첫째 경기자로 IOI와리 게임을 해서 게임을 승리로 이끄는 프로그램을 작성하라. 여러분의 답안과 게임을 같이 하는 평가 프로그램은 언제나 최선을 다해서 게임을 한다. 한눈팔면 평가 프로그램이 이기고 여러분이 질 수도 있다.

입출력

답안 프로그램은 표준 입력 스트림으로부터 입력을 받아 표준 출력 스트림으로 출력한다. 답안 프로그램은 1번 경기자이고, 상대편인 평가 프로그램은 2번 경기자이다. 프로그램이 시작하면 일곱 개의 정수 p1 ... p7이 들어있는 한 줄을 읽어들이도록 한다. 이것이 초기에 각 일곱 구멍에 들어있는 구슬의 개수이다. 게임판에서 구멍은 1부터 7까지 시계 방향 순서로 번호가 매겨져 있다.

그리고 나서 게임은 시작한다. 초기에 양쪽 주머니에는 구슬이 하나도 없다. 게임을 다음과 같이 진행하도록 한다.

• 답안 프로그램 차례라면 자신이 고른 구멍 번호를 표준 출력 스트림으로 출력한다.
• 상대방(평가 프로그램) 차례가 되면 상대방이 고른 구멍의 번호(상대방이 구슬을 모두 가져간 구멍 번호)를 표준 입력 스트림으로 알아온다.

도구

수험 중에 ioiwari2라는 보조 프로그램을 쓸 수 있다. 이 프로그램은 일곱 구멍에 차례대로 구슬이 4, 3, 2, 4, 2, 3, 2개씩 있는 경우에 한해, 2번 경기자로서 게임을 최선을 다해서 해준다. 이 프로그램을 실행하면 가장 먼저 답안 프로그램이 표준 입력 스트림으로 읽어야 하는 일곱 숫자가 출력 스트림으로 나온다. (4 3 2 4 2 3 2)

그리고 나서 이 프로그램은 1번 경기자(답안 프로그램)가 고른 구멍 번호를 표준 입력 스트림으로 입력받고는 자신의 수를 표준 출력 스트림으로 출력한다. 수험자는 답안 프로그램과 ioiwari2를 서로 다른 윈도우로 실행하여 서로 주고받는 내용을 수동으로 조절할 수 있다. 이 프로그램은 주고받은 정보를 ioiwari.out에다 저장해 준다.

(원문에 언어별 지시 사항이 있지만 첫째날 1번 문제의 것과 같은 내용이기 때문에 생략합니다.)

예제

두 경기자가 교대로 게임을 올바르게 여섯 차례 한 예이다.

배점

한 경기에서 답안 프로그램이 이기면 4점, 비기면 2점을 받으며, 그 밖의 경우 0점을 받는다. 이 문제는 각기 다른 데이터로 25번 게임을 하는 걸로 심사를 받으며, 따라서 최대 100점을 받게 된다. 한 데이터당 시간 제한은 1초이며, 메모리 제한은 32MB이다.

3. 스물다섯자 언어

산타클로스와 그의 꼬마 조수들이 주고받는 말은 대개 스물다섯자 언어로 암호화돼 있다. 스물다섯자 알파벳은 Z가 없다는 점만 빼면 로마자 알파벳과 완전히 같다. 순서도 A부터 Y까지 로마자 알파벳과 같다. 스물다섯자 언어의 어휘는 A부터 Y까지 스물다섯 글자의 알파벳이 한 번씩 임의의 순서대로 나열된 꼴이며, 오른쪽-아래로 단어를 써 나갈 수 있다. 예를 들어 ADJPTBEKQUCGLRVFINSWHMOXY란 단어는 아래와 같이 쓸 수 있는 것이다.

A   D   J   P   T
B   E   K   Q   U
C   G   L   R   V
F   I   N   S   W
H   M   O   X   Y

어떤 단어를 오른쪽-아래로 썼을 때, 모든 가로줄(ADJPT 등)과 세로줄(ABCFH 등)의 알파벳이 왼쪽-오른쪽으로, 또는 위-아래로 오름차순이 되면 이것은 스물다섯자 언어의 올바른 어휘이다. 따라서 ADJPTBEKQUCGLRVFINSWHMOXY는 맞는 말이지만, ADJPTBEGQUCKLRVFINSWHMOXY은 그렇지 않다. (둘째, 셋째 세로줄에서 오름차순 순서가 어긋나 있음을 알 수 있다.)

산타클로스에게는 어휘집이 있다. 이 어휘집에는 올바른 스물다섯자 언어 어휘가 오름차순--우리가 일반적으로 생각하는 단어 정렬 방식--으로 모두 나열돼 있으며, 단어 옆에는 사전에 오른 순서를 나타내는 번호도 1부터 매겨져 있다. 예를 들어 ABCDEFGHIJKLMNOPQRSTUVWXY는 번호가 1인 단어이며, ABCDEFGHIJKLMNOPQRSUTVWXY (1과 비교했을 때 T와 U가 바뀜)는 그 다음에 나오는 단어이다. (번호가 2)

이 어휘집은 분량이 어마어마하다. 조합 가능성을 생각해 보면 수긍이 갈 것이다. 그래서 우리는 이 어휘집을 컴퓨터로 올려서 생각해 보고자 한다. 스물다섯자 언어의 아무 어휘를 입력받아 그 어휘가 사전에 몇째로 올라 있는 단어인지를 계산하고, 숫자를 입력받아 사전에 그 순서로 올라가 있는 스물다섯자 언어 어휘를 출력하는 프로그램을 작성하라. 단, 순서가 2³¹을 넘는 단어는 생각하지 않기로 한다.

입력

입력 파일 이름은 twofive.in이며, 여기에는 두 줄이 들어있다. 첫째 줄에는 W 또는 N이라는 한 글자만 있다. 이게 W이면 둘째줄에는 올바른 스물다섯자 언어인 어휘가 들어있다. (스물 다섯 자인 단어) 그렇지 않고 N이면 둘째줄에는 스물다섯자 언어 어휘의 순서를 나타내는 정수가 들어있다.

출력

출력파일 이름은 twofive.out이며, 한 줄을 출력하도록 한다. 입력 파일에 어휘가 들어있었다면, 그 어휘가 스물다섯자 언어의 몇째 어휘인지를 출력하도록 하고, 숫자라면 그 순위에 들어가는 스물다섯자 언어 단어를 출력하도록 한다.

입출력 예제

twofive.in #1
W
ABCDEFGHIJKLMNOPQRSUTVWXY
twofive.out #1
2

twofive.in #2
N
1
twofive.out #2
ABCDEFGHIJKLMNOPQRSTUVWXY

제한

이 문제는 20개의 입력 데이터로 심사를 받으며, 한 데이터당 만점은 5점으로 최대 100점을 받게 된다. 한 데이터당 시간 제한은 0.02초이며, 메모리 제한은 32MB이다.

4. 스코어 게임

스코어는 두 사람이 번갈아가며 같은 말 하나를 게임판 이칸 저칸으로 움직이면서 진행하는 게임이다. 게임판에는 칸이 N개 있으며, 각 칸은 1부터 N까지 번호가 매겨져 있다. 그리고 두 칸이 단방향 화살표로 연결된 곳이 있다. (전산 시간에 배운 그래프를 떠올릴 것.) 각 칸에는 '소유'라는 개념이 있어서, 칸은 두 사람 중 임의의 한 사람이 차지하고 있다. 그리고 모든 칸은 제각기 부호 양인 숫자를 가지고 있다. 이것을 가중치라 하자. 그 수는 칸마다 모두 다르다. 게임은 1번 칸부터 시작한다. 처음에 두 경기자의 점수는 모두 0점이다.

게임은 이렇게 진행된다. 지금 말이 놓여있는 칸을 C라고 하자. 게임 처음에는 C는 1번 칸이다. 1번 칸이 자기 것인 사람부터 게임을 시작한다.

1. C 칸의 가중치가 C칸을 소유한 사람의 지금 점수보다 크면, 그 가중치가 지금 C 칸 소유자의 점수가 된다.(지금 그 사람 차례이든 아니든 상관없이) 그렇지 않으면 C 칸 소유자의 점수는 변하지 않는다. 다른쪽 경기자의 점수는 어떤 경우에도 바뀌지 않는다.
2. 그 뒤 그 사람은 C칸에 밖으로 뻗어있는 화살표 중 하나를 골라 말을 그 화살표가 가리키는 칸으로 옮긴다. 그 칸이 이제 새로운 C칸이 된다. 그 칸의 소유자가 상대방이면 차례는 상대방으로 넘어가게 된다. 그렇지 않으면 그 사람은 자기가 계속 말을 옮길 수 있다.

말이 시작 위치(1번 칸)로 되돌아오면 게임은 끝난다. 이때 점수가 더 높은 사람이 승리자가 된다.

화살표는 언제나 다음과 같은 조건을 만족하도록 뻗어 있다.

• 화살표를 따라가면 지금 말이 놓인 칸에서 다른 칸으로 반드시 나갈 수 있다.
• 화살표만 따라가면 시작점에서 어떤 칸으로든 도달할 수 있다.
• 게임은 유한한 횟수만큼 턴을 거친 후 반드시 끝나게 되어 있다.

이 게임을 해서 승리하는 프로그램을 작성하라. 모든 채점은 여러분이 먼저 하든, 평가 프로그램이 먼저 하든, 답안 프로그램이 반드시 이길수 있는 데이터로 행해진다. 여러분과 게임을 같이 하는 평가 프로그램도 최선을 다해서 게임을 한다. 한눈팔다간 평가 프로그램이 이기고 여러분이 질 수도 있다.

입출력

프로그램은 표준 입력 스트림으로부터 데이터를 입력받고, 출력 역시 표준 출력 스트림으로 한다. 답안 프로그램은 1번 경기자고 상대방은 2번 경기자다. 프로그램이 실행되고 나면 표준 입력 스트림으로부터 다음 정보를 읽어들이도록 한다.

첫줄에는 칸의 개수 N (1<=N<=1000)이 있다. 그리고 그 뒤를 따르는 N줄에는, 그 칸이 다른 칸으로 통하는 화살표에 대한 정보를 나타내는 N개의 정수가 있다. i번 칸에서 j번 칸으로 가는 화살표가 있다면, i째 줄의 j째 숫자는 1이다. 그렇지 않으면 그 숫자는 0이다.

그다음 한 줄에는 N개의 숫자가 있으며, 이 숫자는 각 칸이 누구 것인지를 나타낸다. i째 칸의 소유자가 1번 경기자라면 i째 정수는 1이며, 그렇지 않으면 그 숫자는 2이다.

다음줄에도 역시 N개의 정수가 있으며 이 숫자는 각 칸의 가중치를 나타낸다. i째 정수가 j라면 i째 칸의 가중치가 j라는 말이다. 가중치 j의 범위는 1<=j<=N이며 모든 가중치는 제각기 다르다.

그 뒤 게임을 시작한다. 최초에 말은 1번 칸에 있다. 답안 프로그램은 다음과 같은 지시대로 게임을 진행하다가 말이 다시 1번 칸으로 돌아오면 실행을 끝내야 한다.

• 지금이 답안 프로그램 차례라면, C칸의 화살표가 가리키는 칸 중 가고 싶은 곳(말을 옮기고 싶은 곳) P를 골라, 그 칸의 번호를 표준 출력 스트림으로 출력하도록 한다. (1<=P<=N)
• 상대방이 할 차례라면, 상대방이 말을 옮긴 다음 위치 P를 표준 입력 스트림으로 읽어서 알아오도록 한다. (1<=P<=N)

다음 예를 생각해 보자. 게임판 모양은 그림 1과 같다. 1번 경기자가 소유한 칸은 동그라미로, 2번 경기자가 소유한 칸은 네모로 그려져 있다. 각 칸의 가중치는 그 도형 안에 있으며, 칸의 번호는 도형 바깥에 숫자로 나와 있다. 게임을 한 모습이 아래에 나타나 있다.

stdin     stdout  풀이
4                 N
0 1 0 0           1번칸과 바깥으로 통하는 화살표
0 0 1 1           2번칸과 바깥으로 통하는 화살표
0 0 0 1           3번칸과 바깥으로 통하는 화살표
1 0 0 0           4번칸과 바깥으로 통하는 화살표
1 1 2 2           각 칸의 소유자
1 3 4 2           각 칸의 가중치
           2      1번 경기자(우리)가 말을 옮김 (1점->3점)
           4      1번 경기자가 말을 옮김
1                 2번 경기자가 시작점으로 말을 옮김 (2점) 게임 끝.

게임이 끝나고 1번 경기자는 3점을, 2번 경기자는 2점을 얻었다. 1번 경기자가 이겼다. 1번 경기자가 말을 3번 칸으로 옮기지 않은 것은 현명한 판단이다. 상대방이 4점을 얻을 기회를 주지 않았기 때문이다.

(원문에 언어별 지시 사항이 있지만 첫째날 1번 문제의 것과 같은 내용이기 때문에 생략합니다.)

도구

수험 중에 score2라는 보조 프로그램을 쓸 수 있다. 이 프로그램은 score.in이란 파일에서 게임판 관련 정보를 앞에 있는 순서대로 읽어낸 다음, 그 정보를 같은 형식으로 표준 출력 스트림으로 보내준다. 여러분이 답안 프로그램을 테스트할 때, 같은 게임판 정보를 매번 표준 입력 스트림(키보드)로 입력해야 하는 수고를 덜어주므로 유용할 것이다. 그러고 나서, 이 프로그램은 답안 프로그램의 반응을 표준 입력 스트림으로 읽어들인 뒤, 화살표를 무작위하게 고르는 방식으로--채점 평가 프로그램은 최적의 수로 게임을 함-- 게임을 진행해 주고, 그 결과를 표준 출력 스트림으로 보내준다.

배점

답안 프로그램이 이기면 그 데이터는 만점을 받는다. 그렇지 않으면 0점을 받는다. 채점받을 때 여러분의 답안 프로그램은 제한 시간을 1초 높인 조건하(2초)에서 평가 프로그램이 아닌 다른 프로그램과 게임을 한판 하게 된다. 이때 답안 프로그램의 입출력 내용은 모두 기록된다. 그러고 나서 답안 프로그램은 실제 채점을 위해서 정식 평가 프로그램과 대국한다. 이때 답안 프로그램으로 입력되는 내용은 미리 준비된 파일에서 읽은 내용이다. 답안 프로그램이 출력해 낸 내용은 첫번째 실행 때와 같아야 한다.

이 문제는 각기 다른 데이터로 20번 게임을 하는 걸로 심사를 받으며, 한 데이터당 만점은 5점으로 최대 100점을 받게 된다. 한 데이터당 시간 제한은 1초이며, 메모리 제한은 32MB이다.

5. 이중 암호화

고급 암호화 표준(이하 고암표)에는 새롭고 강력한 암호화 알고리즘이 들어가 있다. 이 암호화 함수는 128비트 데이터 3개를 두고 작업을 행하는데, 평문 p, 열쇠 k를 받아 암호화된 데이터 c를 되돌려준다.

c=E(p,k)

고암표 함수 E의 역함수는 D이다. 따라서 다음과 같은 관계가 성립한다.

D( E(p,k), k)=p,  E( D(c,k), k)=c

이중 고암표에서는 두 개의 서로 다른 키 k1, k2가 암호화하는 데 연속적으로 적용된다.

c2=E( E(p,k1), k2 )

이번 문제는 평문 p, 이중 암호화된 문장 c2를 보고 암호 열쇠인 k1, k2를 알아내는 것이다. 이때, 정수 s가 제시된다. 이것은 풀어야 하는 암호 열쇠의 길이를 알려주는 단서로, 암호 비트에서 왼쪽으로부터 4*s개의 비트만이 우리가 풀어야 하는 암호라는 뜻이다. 이 단서는 k1, k2 모두에 적용되며, 두 열쇠에서 오른쪽 나머지 비트는 모두 0임이 알려져 있다.

고암표 방식대로 암호화하고 해독하는 기능은 라이브러리를 써서 활용할 수 있다.

이번 문제는 각 데이터별로 알아낸 암호 열쇠쌍(k1, k2)만 제출하면 된다. 소스 코드는 심사하지 않는다.

입력

수험자는 풀어야 하는 문제가 담긴 텍스트 파일 10개를 받는다. (double1.in부터 double10.in) 각 입력 파일은 세 줄로 되어 있다. 첫줄에는 정수 s가 있고, 둘째줄에는 평문 p가, 셋째줄에는 p를 두번 암호화시킨 c2가 있다. 이진 파일 내용을 텍스트 파일에 저장하기는 힘드므로 각 데이터 내용은 한 바이트당 2바이트인 16진수 숫자 문자열로 기록된다. (0~9, A~F) 라이브러리에는 숫자 문자열을 비트 데이터로 바꿔주는 함수가 있다. 모든 입력 파일은 암호를 알아낼 수 있게 되어 있다.

출력

각 입력 파일에 따라 출력 파일을 만들어서 제출하면 된다. 각 출력 파일에는 세 줄을 넣도록 한다. 첫줄에는 다음과 같은 문장을 넣는다. I는 여기에 해당하는 입력 파일의 번호이다.

#FILE double I

둘째줄에는 k1, 셋째줄에는 k2의 내용을 16진수 숫자 문자열로 바꿔서 기록한다. 이렇게 해서 c2= E( E(p, k1), k2)가 성립하면 되는 것이다. 물론 라이브러리는 비트 데이터를 숫자 문자열로 바꿔주는 함수도 제공한다. 답이 여러 개 있더라도 한 가지만 출력하면 된다.

예제

예제로 0번이란 번호를 붙여 보았다.

double0.in
1
00112233445566778899AABBCCDDEEFF
6323B4A5BC16C479ED6D94F5B58FF0C2

 그에 따라 있을 수 있는 출력 모습

double0.out
#FILE double 0
A0000000000000000000000000000000
70000000000000000000000000000000

라이브러리

프리파스칼 라이브러리

type
  HexStr = String [ 32 ]; { only '0'..'9', 'A'..'F' }
  Block  = array [ 0..15 ] of Byte; { 128 bits }

procedure HexStrToBlock ( const hs: HexStr; var b: Block );
procedure BlockToHexStr ( const b: Block; var hs: HexStr );
procedure Encrypt ( const p, k: Block; var c: Block );
  { c = E(p,k) }
procedure Decrypt ( const c, k: Block; var p: Block );
  { p = D(c,k) }

GNU C/C++ 라이브러리

typedef char HexStr[33]; /* '0'..'9', 'A'..'F', '\0'-terminated */
typedef unsigned char Block[16];  /* 128 bits */
 
void hexstr2block ( const HexStr hs, /* out-param */ Block b );
void block2hexstr ( const Block b, /* out-param */ HexStr hs );
void encrypt ( const Block p, const Block k, /* out-param */ Block c );
  /* c = E(p,k) */
void decrypt ( const Block c, const Block k, /* out-param */ Block p );
  /* p = D(c,k) */

언어별로 라이브러리 사용법을 보여주는 aestoolc.c와 aestoolp.pas가 제공된다.

제한

암호 열쇠 문자에 대한 단서를 제공하는 정수 s의 범위는 1<=s<=5이다.

이 문제는 10개의 데이터로 심사를 받으며, 프로그램의 실행 과정으로 심사를 받는 게 아니라 여러분이 풀어서 제출한 암호가 맞는지 틀리는지의 여부로만 심사를 하게 된다. 따라서 어떤 프로그램을 짜든 암호만 풀어내면 된다. 첫째 데이터만 1점이며, 나머지 9개의 데이터는 11점으로, 합계 최대 100점을 받는다.

힌트: 제대로 된 프로그램은 암호를 10초 안으로 복원해 낼 수 있다.

6. 컨테이너 보관

핀란드에 첨단 기술을 보유한 회사가 하나 있다. 이 회사는 커다란 직사각형 모양의 창고를 두고 있다. 창고의 좌우상하 각 모서리를 편의상 왼쪽, 꼭대기, 오른쪽, 밑바닥이라고 일컫겠다. 창고는 크기가 모두 같은 정사각형 격자 구역으로 분할돼 있다. 창고의 가로줄은 꼭대기에서 밑바닥까지 정수 1, 2, ...의 순으로 번호가 매겨져 있으며, 세로줄 역시 왼쪽에서 오른쪽으로 1, 2, ...의 순으로 번호가 매겨져 있다.

창고에는 귀중한 기계 장비를 담은 컨테이너가 보관된다. 컨테이너들은 제각기 다른 번호가 부여된다.(꼭 1부터 N까지 빠짐없이 번호가 매겨지는 것은 아님) 컨테이너 하나는 정확히 정사각형 칸 하나를 차지한다. 창고는 충분히 크기 때문에, 창고에 집어넣어야 하는 컨테이너 수는 창고의 가로줄 수보다 작고, 세로줄 수보다도 작다. 컨테이너를 창고 밖으로 꺼내는 일은 없으며, 이 문제에서는 새 컨테이너을 2차원적으로 창고 안으로 집어넣는 경우만 생각한다. 창고 입구는 맨 왼쪽 꼭대기이다.

그리고 창고에는 일꾼과 관리자가 있다. 일꾼은 컨테이너를 식별 번호로 찾을 수 있게 하기 위해, 왼쪽 꼭대기 주위에 있는 컨테이너들을 다음과 같은 방법으로 정렬한다.

이번에 집어넣어야 하는 컨테이너의 번호가 k라고 하자. 일꾼은 맨 윗줄부터 시작하여 아래로 내려간다. 각 줄을 왼쪽부터 가로로 훑으며 번호가 k보다 큰 컨테이너를 찾는다. 그런 게 없으면 k번 컨테이너는 그줄 맨 오른쪽에 쌓아둔다. 반면, k보다 번호가 큰 l이라는 컨테이너가 발견되면 l이 있던 곳에 k를 두고, l은 그 다음 줄로 밀려나, 지금까지 했던 방법을 거기서부터 반복하여 다른 곳에 놓이게 된다. (아랫줄에는 l 때문에 밀려나는 컨테이너가 또 생기고 그런 식으로 반복됨.) 그리고, 컨테이너가 하나도 없는 맨 아랫줄에 도달하면, 일꾼은 이 컨테이너를 그줄 맨 왼쪽에 놓아둔다.

번호가 3, 4, 9, 2, 5, 1인 컨테이너가 차례대로 들어왔다면 창고에 컨테이너들이 들어가 있는 모습은 다음과 같게 된다.

1 4 5     ∵ 3    3 4    3 4 9     2 4 9         2 4 5             1 4 5 (2가 밀려나고,
2 9                                3  (2때문에   3 9 (9가 밀려남)  2 9    2 때문에 3이 또 밀려남)
3                                   3이 밀려남)                    3

관리자가 일꾼에게 와서 이런 이야기를 나눈다.

"5번 컨테이너는 4번보다 먼저 왔는가?"
"아닙니다요, 그건 있을 수 없어요."
"컨테이너가 쌓인 모양만 보고 이것들이 도착한 정확한 순서를 알 수 있는가 보군."
"꼭 그런 건 아니죠. 지금 쌓여 있는 컨테이너들은 3, 2, 1, 4, 9, 5와 같은 순서로 왔을 수도 있고, 3, 2, 1, 9, 4, 5일 수도 있고... 아무튼 있을 수 있는 열네 가지 경우 중 한 가지 순서대로 왔을 겁니다."

더 말하다가는 자신의 무식함만 더 드러낼 것 같아서 관리자는 그냥 가 버린다. 자, 여러분은 이 관리자를 도와야 한다. 컨테이너가 창고에 놓여 있는 모양을 입력받아서 이들이 어떤 순서대로 도착했을지 가능한 경우를 모두 추정하는 프로그램을 작성하라. (컨테이너가 3, 4, 9, 2, 5, 1의 순으로 왔을 때만 1 4 5: 2 9: 3과 같은 모양이 생기는 게 아니기 때문이다. 그리고 창고의 가로 세로 크기는 무한하다고 생각할 것.)

입력

입력 파일 이름은 depot.in이다. 첫줄에는 컨테이너가 놓여있는 줄 수 R이 들어있다. 그리고 다음에는 R개의 줄이 따르며, 각 줄에는 창고의 그 세로줄에 들어있는 컨테이너의 개수 M부터 시작하여, 그 M개의 컨테이너들의 번호가 왼쪽부터 쭉 나열돼 있다. 컨테이너의 식별번호 I는 1<=I<=50을 만족한다. 창고에 있는 서로 다른 컨테이너의 개수 N은 1<=N<=13이다.

출력

출력 파일 이름은 depot.out이다. 출력 파일에는 가능한 경우를 최대한 많이 찾아서 그 경우를 출력하도록 한다. 각 줄에는 컨테이너들이 도착한 순서를 컨테이너 식별 번호로 표현한 정수 N개가 있다. (먼저 도착한 것을 왼쪽에 배치) 답으로 출력한 순서 항목 중에 서로 중복하는 것이 없도록 한다.

입출력 예제

depot.in #1
3
3 1 4 5
2 2 9
1 3
depot.out #1
3 2 1 4 9 5
3 2 1 9 4 5
3 4 2 1 9 5
3 2 4 1 9 5
3 2 9 1 4 5
3 9 2 1 4 5
3 4 2 9 1 5
3 4 9 2 1 5
3 2 4 9 1 5
3 2 9 4 1 5
3 9 2 4 1 5
3 4 2 9 5 1
3 4 9 2 5 1
3 2 4 9 5 1
3 2 9 4 5 1
3 9 2 4 5 1

depot.in #2
2
2 1 2
1 3
depot.out #2
3 1 2
1 3 2

배점

출력 파일의 답안 중에 있을 수 없는 순서가 하나라도 있거나, 가능한 순서가 하나도 없으면 그 입력 데이터에 대한 점수는 0점이 된다. 그렇지 않고, 가능한 순서를 하나도 빠짐없이 찾아냈을 뿐만 아니라 서로 중복하는 것도 없으면 4점을 받는다. 한편, 가능한 순서를 최소한 반 이상 찾아내고 서로 중복하는 게 없으면 2점을 받는다. 그리고 하나 이상 반 이하를 찾아냈거나, 같은 답을 중복해서 출력한 게 발견되면 1점을 받는다.

이 문제는 25개의 입력 데이터로 심사를 받으며, 한 데이터당 만점은 4점으로 최대 100점을 받게 된다. 한 데이터당 시간 제한은 0.3초이며, 메모리 제한은 32MB이다.