Output-only 유형 문제

Output-only 유형 문제는 프로그램의 소스 코드를 제출하는 대신, 미리 공개된 입력 데이터에 대한 정답 텍스트 파일만을 제출하는 형태입니다.

문제 해결 방식

Output-only 유형의 문제를 풀이하는 방식은 앞선 Batch 문제와 근본적으로 다릅니다. 채점 서버에서 실행될 코드를 작성하는 것이 아니라, 문제에서 미리 공개한 고정된 입력 데이터를 로컬 환경에서 직접 처리하여 최종 출력 파일만 만들어 제출하기 때문입니다.

예를 들어 미로에서 시작점 S부터 도착점 E까지의 경로를 찾는 문제를 생각해 봅시다. 참가자는 길 찾기 알고리즘 코드를 제출하는 것이 아닙니다. 파일로 주어진 미로를 바탕으로 유효한 이동 경로를 로컬에서 알아낸 뒤, 그 경로 문자열이 담긴 텍스트 파일만을 서버에 제출합니다.

01.in:

3 3
S..
.#.
..E

01.out:

RRDD

이때 출력 파일을 만들어내는 방법에는 아무런 제한이 없습니다. 직접 작성한 프로그램을 로컬에서 실행하여 출력 파일을 생성해도 되고, 데이터의 크기가 작거나 규칙이 단순하다면 손으로 직접 계산해도 됩니다.

가장 중요한 차이는 프로그램의 실행 시간(Time Limit) 제한을 서버에서 강제받지 않는다는 점입니다. 채점은 오직 제출된 출력 파일의 내용만으로 이루어지므로, 참가자는 로컬 컴퓨터에서 충분한 시간을 들여 복잡한 연산을 수행하고 최적의 결과값을 도출할 수 있습니다.

IOI 환경과 제공 파일 (providing.zip)

Output-only 방식을 사용하는 대회에서는 참가자가 모든 테스트 케이스를 로컬에서 직접 처리할 수 있도록 압축 파일 형태의 자료를 제공합니다. 이 압축 파일에는 답을 구해야 할 입력 데이터와 결과를 확인하는 데 필요한 도구가 포함되어 있습니다.

1. 입력 데이터 파일 (01.in, 02.in, ...)

참가자가 읽어 들여 답을 구해야 할 실제 테스트 케이스 입력 데이터 파일들입니다. 일반적인 Batch 문제에서는 이러한 입력 파일이 채점 서버에 비밀로 숨겨져 있지만, Output-only 문제에서는 참가자가 직접 처리해야 하므로 모든 입력 파일이 그대로 공개됩니다.

2. 검증기 (checker)

문제에 따라 정답이 여러 개일 수 있거나 조건을 만족하는 출력을 자유롭게 구성할 수 있는 경우, 참가자가 자신이 만든 출력 파일이 정답으로 인정되는지 로컬 환경에서 미리 확인해 볼 수 있도록 검증기 프로그램이나 그 소스 코드가 동봉됩니다.

예를 들어 미로 경로 찾기 문제의 검증기는 입력 파일과 참가자의 출력 파일을 함께 읽어, 해당 경로가 벽(#)을 통과하지 않고 미로를 벗어나지 않으면서 S에서 E까지 올바르게 도달하는지 판정합니다.

./checker 01.in 01.out

테스트 케이스와 서브태스크

제출된 출력 파일은 서버에서 각각의 테스트 케이스 번호에 맞춰 평가됩니다. 예를 들어 미로 경로 찾기 문제라면, 01.in 파일에 주어진 미로를 읽고 이에 맞는 경로를 찾아 01.out 파일에 RRDD를 적어 제출하는 과정 하나가 독립된 테스트 케이스입니다.

Output-only 문제는 대부분 정답이 하나로 정해지지 않고 "더 좋은 답"이 존재하는 최적화 문제로 출제됩니다. 이러한 문제에서는 각각의 입력 파일(또는 서브태스크) 하나하나가 독립적으로 채점되며, 검증기가 참가자의 출력이 얼마나 우수한지를 점수로 환산하여 부분 점수를 부여합니다. 따라서 한 번에 완벽한 답을 제출할 필요가 없으며, 참가자는 로컬에서 시간을 들여 각 출력의 품질을 조금씩 개선해 나가며 점수를 점진적으로 높여 나가게 됩니다.

부분 점수 채점의 예시

앞서 살펴본 미로 경로 찾기 문제가, 단순히 도착하기만 하면 되는 것이 아니라 가능한 한 짧은 경로를 찾는 최적화 문제로 출제되었다고 가정해 봅시다. 이 경우 부분 점수가 어떻게 매겨지는지 가상의 지문을 통해 살펴보겠습니다.

이 문제에서는 각각의 입력 파일 하나가 독립된 서브태스크가 되며, 서브태스크마다 미로의 크기와 함께 목표 경로 길이 $K$가 정해집니다. 참가자가 길이 $K$ 이하의 경로를 찾아내면 해당 서브태스크의 만점을 얻고, 그에 못 미치더라도 경로의 길이에 따라 부분 점수를 받습니다.

서브태스크	점수	미로 크기	목표 길이 $K$
1	20	$10\times 10$	18
2	20	$50\times 50$	96
3	20	$100\times 100$	190
4	20	$500\times 500$	980
5	20	$1000\times 1000$	1960

참가자가 제출한 경로가 벽을 통과하거나 미로를 벗어나는 등 유효하지 않다면 해당 서브태스크는 0점으로 처리됩니다. 유효한 경로를 제출했다면, 그 경로의 길이를 $L$이라 할 때 해당 서브태스크의 점수는 다음과 같이 계산됩니다.

$$20\cdot min(1,\frac{K}{L})$$

즉 목표 길이 $K$ 이하의 경로를 찾아내면 만점 20점을 받고, 그보다 긴 경로를 제출하면 길이 $L$에 반비례하여 부분 점수를 받습니다. 예를 들어 서브태스크 1($K=18$)에서 길이 24인 경로를 제출했다면 $20\cdot \frac{18}{24}=15$점을 얻고, 이후 더 짧은 길이 18의 경로를 찾아내면 만점인 20점을 얻게 됩니다.

이처럼 참가자는 일단 도착에 성공하는 경로로 부분 점수를 확보한 뒤, 로컬에서 시간을 들여 더 짧은 경로를 찾아 점수를 점진적으로 끌어올릴 수 있습니다.

제출 방법

Output-only 문제에서는 제공된 입력 파일의 개수만큼 여러 개의 출력 파일을 생성하게 됩니다. 01.in, 02.in 등 다수의 입력 파일에 대해 로컬에서 01.out, 02.out 등의 출력 파일들을 만들어냅니다.

결과가 준비되면, 대회나 시스템에서 안내하는 방식에 따라 여러 개의 출력 파일을 하나로 압축(output.zip 등)하거나 여러 파일을 선택하여 서버에 업로드합니다. 대부분의 시스템에서는 모든 출력 파일을 한꺼번에 제출하지 않고, 특정 입력 파일에 대한 출력 파일 하나만 따로 제출하는 방식도 허용합니다.