Interactive 유형 문제

Interactive 유형 문제는 참가자의 프로그램이 채점기와 대화하듯 질문을 던지고 답을 받으며, 그 답들을 단서 삼아 정답에 다가가는 형태입니다.

문제 해결 방식

지금까지 본 함수 구현 방식에서는 채점기가 입력을 건네주면 참가자의 함수가 답을 계산해 돌려주고 그것으로 끝이었습니다. Interactive 유형은 이 한 번의 주고받음을 여러 번의 대화로 늘린 형태입니다. 참가자의 함수는 처음부터 모든 정보를 받지 못합니다. 대신 채점기가 미리 마련해 둔 함수를 호출해 한 조각씩 정보를 캐물어야 하고, 채점기는 그 물음에만 답을 돌려줍니다. 이렇게 채점기에게 던지는 한 번의 물음을 질의(query)라고 부릅니다.

어떤 문제인지 손에 잡히도록, 채점기가 1부터 100 사이의 정수 하나를 마음속에 정해 두고 그 값을 맞히게 하는 상황을 살펴보겠습니다. 정해진 값을 $X$라고 하면, 참가자는 $X$를 곧바로 들여다볼 수 없고 다음 질의 함수를 통해서만 $X$의 단서를 모을 수 있습니다.

• is_at_most(x) — 채점기가 마음속에 정한 $X$가 $x$ 이하이면 true, $x$보다 크면 false를 알려 줍니다.

참가자가 완성해야 하는 것은 find_number() 함수입니다. 이 함수는 is_at_most를 거듭 호출해 가며 단서를 좁히고, 끝내 $X$가 무엇인지 확신하게 되면 그 값을 반환합니다.

이 대화에는 두 가지 규칙이 따라붙습니다. 첫째, 모든 정보 교환은 채점기가 제공하는 함수를 통해서만 이루어지므로 cin이나 cout 같은 표준 입출력을 직접 건드려서는 안 됩니다. 함수 안에서 화면에 무언가를 출력하는 순간 채점기와의 약속된 통신이 헝클어져 오답으로 이어집니다. 디버깅을 위해 잠시 출력문을 넣었더라도 제출 전에는 흔적 없이 지워야 합니다. 둘째, 질의에는 대개 횟수 상한이 걸립니다. 예컨대 위 문제에서 is_at_most를 7번까지만 부를 수 있다고 정해졌다고 합시다.

질의 한 번이 귀하다면, 한 번 물을 때마다 후보의 폭을 가능한 한 크게 잘라내야 합니다. 매번 후보 구간의 한가운데 값을 물어 절반을 떨어내는 이분 탐색(Binary Search)을 쓰면, 100개의 후보도 $\lceil {\log }_{2}100\rceil =7$번 만에 하나로 줄어듭니다. 후보 구간을 low부터 high까지로 두고 그 중앙값 mid를 물었을 때, 답이 true라면 $X$는 mid 이하이니 high를 mid까지 당기고, false라면 $X$는 mid를 넘으니 low를 mid + 1로 올립니다. 이 과정을 구간이 한 점으로 모일 때까지 반복하면 남은 그 값이 곧 $X$입니다. 상한을 넘겨 질의하면 오답이 되며, 같은 정답이라도 더 적은 질의로 알아낼수록 높은 점수를 주는 문제도 적지 않으므로, 결국 관건은 "얼마나 영리하게 적게 묻느냐"입니다.

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

Interactive 문제도 참가자가 로컬에서 똑같은 환경을 흉내 내 볼 수 있도록 압축 자료를 제공합니다. 안에는 질의에 응답해 주는 채점기와, 참가자가 빈칸을 채워 넣을 스켈레톤 코드가 들어 있습니다.

1. 스켈레톤 코드 (solution.cpp)

참가자의 손이 닿는 유일한 파일입니다. 맨 위에서 채점기 쪽 질의 함수 is_at_most를 사용할 것이라고 미리 선언해 두고, find_number 안에서 그 함수를 불러 가며 답을 찾아 나갑니다.

bool is_at_most(int x);

int find_number() {
    int low = 1;
    int high = 100;

    while (low < high) {
        int mid = (low + high) / 2;
        if (is_at_most(mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }

    return low;
}

2. 채점기 (grader.cpp)

main과 더불어 질의 함수 is_at_most의 진짜 알맹이가 담긴 파일입니다. 입력으로 받은 숨은 값(hidden)을 보관해 두고 질의가 들어올 때마다 답해 주며, 그때마다 질의 횟수를 하나씩 세어 상한을 넘지 않았는지 지켜봅니다. 마지막에는 find_number가 내놓은 값이 숨긴 값과 같은지를 따져 통과 여부를 판정합니다.

#include <iostream>
using namespace std;

int find_number();

namespace {
int hidden;
const int question_limit = 7;
int question_count = 0;
}

bool is_at_most(int x) {
    ++question_count;
    return hidden <= x;
}

int main() {
    cin >> hidden;

    const int answer = find_number();
    if (answer != hidden) {
        cerr << "wrong answer: " << answer << '\n';
        return 1;
    }
    if (question_count > question_limit) {
        cerr << "too many questions: " << question_count << '\n';
        return 1;
    }
    cout << "ok " << question_count << '\n';
    return 0;
}

3. 예제 입출력 파일 (sample.in, sample.out)

로컬에서 채점기를 돌려 보고 결과를 맞춰 볼 수 있도록 예제 입출력이 함께 들어 있습니다. 입력 파일에는 채점기가 숨길 정수 하나가 적혀 있습니다.

sample.in:

73

sample.out:

ok 7

질의 횟수와 채점

서버에서는 숨긴 값을 달리한 여러 테스트 케이스로 코드를 채점합니다. 각 케이스에서 참가자의 함수가 허용된 질의 횟수 안에 올바른 값을 반환해야만 그 케이스를 통과하며, 횟수를 넘기거나 엉뚱한 값을 돌려주면 통과하지 못합니다.

여러 테스트 케이스를 묶어 서브태스크(Subtask)를 이루는 구조도 Batch 문제와 다르지 않습니다. 차이가 있다면, Interactive 문제는 서브태스크마다 허용 질의 횟수를 달리 잡아 "더 적게 묻는 풀이"에 더 큰 점수를 얹어 주는 경우가 흔하다는 점입니다.

서브태스크	점수	질의 횟수 제한
1	30	100번 이하
2	70	7번 이하

이런 지문이라면 후보를 하나씩 끝까지 물어보는 단순한 방법으로도 서브태스크 1의 30점은 챙길 수 있지만, 나머지 70점까지 가져가려면 질의를 7번 안으로 압축하는 이분 탐색 같은 전략이 반드시 필요합니다.

컴파일 및 실행 방법

함수 구현 방식과 마찬가지로 채점기 파일과 작성한 스켈레톤 파일을 함께 컴파일해야 합니다. solution.cpp와 grader.cpp가 주어졌을 때 컴파일 명령어는 다음과 같습니다.

g++ solution.cpp grader.cpp -std=gnu++20 -O2 -pipe -Wall -o main

컴파일이 완료되면 실행 파일(main)이 생성됩니다. 생성된 프로그램에 예제 입력 파일(sample.in)을 리다이렉션하여 결과를 확인합니다. 아래와 같이 실행하면 채점기가 find_number를 호출하고, 그 함수가 던지는 질의에 응답해 가며 정답 여부와 질의 횟수를 판정합니다. 제한 횟수 안에 정답을 맞히면 호출 횟수와 함께 ok가 출력됩니다.

./main < sample.in
ok 7

참고로, 제공되는 grader.cpp는 로컬 테스트 용도이므로 sample.in의 값을 바꿔 가며 여러 상황을 직접 시험해 볼 수 있습니다. 단, 실제 채점 서버에서는 원본 채점기가 사용된다는 점에 주의해야 합니다.