최후의 만찬

레오나르도는 가장 유명한 벽화인 최후의 만찬을 작업할 때 매우 바빴다. 하루 일과 중 가장 먼저 하는 일 중 하나는 그날 남은 작업 동안 어떤 템페라 물감을 쓸지 정하는 것이었다. 그는 많은 색이 필요했지만 비계 위에는 제한된 수의 색만 올려둘 수 있었다. 조수는 여러 일 중에서도 비계에 올라가 레오나르도에게 물감을 전해 주고, 다시 내려와 바닥의 알맞은 선반에 물감을 돌려놓는 일을 맡았다.

이 문제에서는 조수를 돕는 두 개의 별도 프로그램을 작성해야 한다. 첫 번째 프로그램은 레오나르도의 지시(그날 레오나르도가 필요로 할 색의 나열)를 받아서 조언이라는 짧은 비트열을 만든다. 조수는 하루 동안 레오나르도의 요청을 처리하면서 레오나르도의 앞으로의 요청을 볼 수 없고, 첫 번째 프로그램이 만든 조언만 볼 수 있다. 두 번째 프로그램은 조언을 받은 뒤 레오나르도의 요청을 온라인 방식으로, 즉 하나씩 받아서 처리한다. 이 프로그램은 조언이 무엇을 뜻하는지 이해하고, 그것을 이용해 최선의 선택을 해야 한다. 자세한 내용은 아래에 설명되어 있다.

선반과 비계 사이에서 물감 옮기기

단순화한 상황을 생각하자. 0부터 N - 1까지 번호가 붙은 N가지 색이 있고, 레오나르도는 하루에 정확히 N번 조수에게 새로운 색을 요청한다. 레오나르도가 요청한 N개 색의 나열을 C라고 하자. 따라서 C는 0 이상 N - 1 이하의 수 N개로 이루어진 나열로 볼 수 있다. 어떤 색은 C에 전혀 나타나지 않을 수 있고, 어떤 색은 여러 번 나타날 수 있다.

비계는 항상 가득 차 있으며, N가지 색 중 K가지를 담고 있다. 여기서 K < N이다. 처음에 비계에는 0부터 K - 1까지의 색이 있다.

조수는 레오나르도의 요청을 하나씩 처리한다. 요청된 색이 이미 비계에 있으면 조수는 쉴 수 있다. 그렇지 않으면 선반에서 요청된 색을 집어 비계로 옮겨야 한다. 물론 비계에는 새 색을 놓을 자리가 없으므로, 조수는 비계에 있는 색 하나를 골라 비계에서 선반으로 되돌려야 한다.

레오나르도의 최적 전략

조수는 가능한 한 많이 쉬고 싶어 한다. 쉴 수 있는 요청의 수는 처리 과정에서 내리는 선택에 따라 달라진다. 더 정확히 말하면, 조수가 비계에서 색을 치워야 할 때마다 어떤 색을 고르느냐에 따라 앞으로의 결과가 달라질 수 있다. 레오나르도는 C를 알고 있다는 전제에서 목표를 달성하는 방법을 조수에게 설명한다. 비계에서 치울 색을 고르는 가장 좋은 방법은 현재 비계에 있는 색과 C에 남은 색 요청을 살펴보는 것이다. 비계에 있는 색 중에서 다음 규칙에 따라 색을 골라야 한다.

• 비계에 있는 색 중 앞으로 전혀 필요하지 않을 색이 있으면, 조수는 그런 색을 비계에서 치워야 한다.
• 그렇지 않으면, 비계에서 치울 색은 앞으로 가장 나중에 필요해질 색이다. 즉, 비계에 있는 각 색에 대해 앞으로 처음 나타나는 위치를 찾는다. 선반으로 되돌릴 색은 그중 가장 나중에 필요해지는 색이다.

레오나르도의 전략을 따르면 조수가 가능한 한 많이 쉴 수 있다는 것을 증명할 수 있다.

예제 1

N = 4, 즉 색이 4가지(0부터 3까지)이고 요청도 4번이라고 하자. 요청의 나열이 C = (2, 0, 3, 0)이라고 하자. 또한 K = 2라고 하자. 즉, 레오나르도는 한 번에 색 2가지를 담을 수 있는 비계를 가지고 있다. 위에서 말한 대로 비계에는 처음에 색 0과 1이 있다. 비계의 내용을 다음과 같이 쓰자: [0, 1]. 조수가 요청을 처리할 수 있는 한 가지 방법은 다음과 같다.

• 첫 번째로 요청된 색(번호 2)은 비계에 없다. 조수는 그것을 비계에 올리고 색 1을 비계에서 치우기로 한다. 현재 비계는 [0, 2]이다.
• 다음으로 요청된 색(번호 0)은 이미 비계에 있으므로 조수는 쉴 수 있다.
• 세 번째 요청(번호 3)에 대해 조수는 색 0을 치우고, 비계는 [3, 2]가 된다.
• 마지막으로 요청된 색(번호 0)을 선반에서 비계로 옮겨야 한다. 조수는 색 2를 치우기로 하고, 비계는 이제 [3, 0]이 된다.

위 예에서 조수는 레오나르도의 최적 전략을 따르지 않았다. 최적 전략은 세 번째 단계에서 색 2를 치우는 것이므로, 조수는 마지막 단계에서 다시 쉴 수 있었을 것이다.

조수의 기억이 제한적일 때의 전략

아침에 조수는 레오나르도에게 C를 종이에 적어 달라고 부탁해서, 그것을 보고 최적 전략을 찾아 따를 수 있게 해 달라고 한다. 하지만 레오나르도는 자신의 작업 기법을 비밀로 유지하는 데 집착해서, 조수에게 종이를 주기를 거부한다. 그는 조수가 C를 읽고 기억해 보는 것만 허락했다.

안타깝게도 조수의 기억력은 매우 나쁘다. 그는 많아야 M비트까지만 기억할 수 있다. 일반적으로 이 때문에 조수는 전체 나열 C를 복원하지 못할 수 있다. 따라서 조수는 자신이 기억할 비트열을 계산하는 영리한 방법을 마련해야 한다. 이 비트열을 조언열이라고 부르고 A로 나타내자.

예제 2

아침에 조수는 C가 적힌 레오나르도의 종이를 가져다가 나열을 읽고 필요한 선택을 모두 할 수 있다. 그가 선택할 수 있는 한 가지 방법은 각 요청 이후의 비계 상태를 살펴보는 것이다. 예를 들어 예제 1에서 제시한 (최적이 아닌) 전략을 쓰면 비계 상태의 나열은 [0, 2], [0, 2], [3, 2], [3, 0]이 된다. (조수는 비계의 처음 상태가 [0, 1]이라는 것을 알고 있다.)

이제 M = 16, 즉 조수가 16비트의 정보까지 기억할 수 있다고 하자. N = 4이므로 각 색을 2비트로 저장할 수 있다. 따라서 위의 비계 상태 나열을 저장하기에 16비트로 충분하다. 조수는 다음과 같은 조언열을 계산한다: A = (0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0).

나중에 조수는 이 조언열을 해독해서 자신의 선택에 이용할 수 있다.

(물론 M = 16이면 조수는 사용할 수 있는 16비트 중 8비트만 써서 전체 나열 C를 기억하기로 할 수도 있다. 이 예는 좋은 해법을 알려 주지 않으면서 조수에게 다른 선택지가 있을 수 있다는 것을 보여 주기 위한 것이다.)

문제 설명

같은 프로그래밍 언어로 두 개의 별도 프로그램을 작성해야 한다. 이 프로그램들은 차례로 실행되며, 실행 중에는 서로 통신할 수 없다.

첫 번째 프로그램은 조수가 아침에 사용하는 프로그램이다. 이 프로그램은 나열 C를 받아서 조언열 A를 계산해야 한다.

두 번째 프로그램은 조수가 낮 동안 사용하는 프로그램이다. 이 프로그램은 조언열 A를 받은 뒤 레오나르도의 요청 나열 C를 처리해야 한다. 나열 C는 이 프로그램에 한 번에 하나의 요청씩만 드러나며, 각 요청은 다음 요청을 받기 전에 처리해야 한다.

더 정확히 말하면, 첫 번째 프로그램에서는 배열 C(0 이상 N - 1 이하의 정수 N개), 비계에 있는 색의 수 K, 조언에 쓸 수 있는 비트 수 M을 입력으로 받는 단일 루틴 ComputeAdvice(C, N, K, M)를 구현해야 한다. 이 프로그램은 많아야 M비트로 이루어진 조언열 A를 계산해야 한다. 그런 다음 A의 각 비트를 순서대로 다음 루틴을 호출해서 시스템에 전달해야 한다.

• WriteAdvice(B) — 현재 조언열 A에 비트 B를 덧붙인다. (이 루틴은 많아야 M번 호출할 수 있다.)

두 번째 프로그램에서는 단일 루틴 Assist(A, N, K, R)를 구현해야 한다. 이 루틴의 입력은 조언열 A, 위에서 정의한 정수 N과 K, 그리고 비트 단위로 나타낸 조언열 A의 실제 길이 R(R ≤ M)이다. 이 루틴은 주어지는 다음 루틴을 이용해 조수를 위한 전략을 수행해야 한다.

• GetRequest() — 레오나르도가 요청한 다음 색을 반환한다. (앞으로의 요청에 대한 정보는 드러나지 않는다.)
• PutBack(T) — 비계에 있는 색 T를 선반으로 되돌린다. 이 루틴은 T가 현재 비계에 있는 색일 때만 호출할 수 있다.

Assist 루틴은 실행될 때 GetRequest를 정확히 N번 호출해서 레오나르도의 요청을 순서대로 하나씩 받아야 한다. GetRequest를 호출한 뒤 반환된 색이 비계에 없으면, 원하는 T를 골라 PutBack(T)도 호출해야 한다. 그렇지 않으면 PutBack을 호출해서는 안 된다. 이를 지키지 않으면 오류로 간주되어 프로그램이 종료된다. 처음에 비계에는 0부터 K - 1까지의 색이 있다는 것을 기억하자.

두 루틴이 모든 제약을 지키고 PutBack 호출 횟수가 레오나르도의 최적 전략과 정확히 같으면 해당 테스트 케이스는 해결된 것으로 본다. 같은 PutBack 호출 횟수를 달성하는 전략이 여러 개라면, 프로그램은 그중 어느 것을 수행해도 된다. 즉, 똑같이 좋은 다른 전략이 있다면 레오나르도의 전략을 따르지 않아도 된다.

예제 3

예제 2에 이어서, ComputeAdvice에서 A = (0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0)을 계산했다고 하자. 이것을 시스템에 전달하려면 다음과 같이 호출해야 한다: WriteAdvice(0), WriteAdvice(0), WriteAdvice(1), WriteAdvice(0), WriteAdvice(0), WriteAdvice(0), WriteAdvice(1), WriteAdvice(0), WriteAdvice(1), WriteAdvice(1), WriteAdvice(1), WriteAdvice(0), WriteAdvice(1), WriteAdvice(1), WriteAdvice(0), WriteAdvice(0).

그러면 두 번째 루틴 Assist가 실행되면서 위의 조언열 A와 N = 4, K = 2, R = 16을 받는다. Assist 루틴은 정확히 N = 4번 GetRequest를 호출해야 한다. 또한 요청 중 일부 뒤에는 알맞은 T를 골라 PutBack(T)를 호출해야 한다.

아래 표는 예제 1의 (최적이 아닌) 선택에 대응하는 호출 순서를 보여 준다. 빗금은 PutBack을 호출하지 않음을 나타낸다.

실제 IOI 문제와는 다르게 파일 하나에 모두 모아서 제출해야 한다.