Bài tương tác (Interactive Problem)

Bài tương tác là gì?

Trong bài tương tác, chương trình của thí sinh không đọc toàn bộ input rồi in output như bài thường. Thay vào đó, chương trình giao tiếp qua lại với hệ thống: gửi truy vấn, nhận phản hồi, rồi dựa trên phản hồi để quyết định bước tiếp theo.

Ví dụ: Tìm một số ẩn $x$ bằng cách hỏi "số $y$ có nhỏ hơn $x$ không?" tối đa 30 lần → tìm nhị phân.

Kiến trúc trên CTOJ

┌──────────┐    stdin/stdout    ┌──────────────┐
│  Thí sinh │ ◄────────────────► │  Interactor  │
│  (code)   │                    │  (plain C++) │
└──────────┘                    └──────┬───────┘
                                       │ đọc
                                       ▼
                                 ┌──────────┐
                                 │  .in file │
                                 └──────────┘

• Interactor: Chương trình C++ chạy song song với code thí sinh, đóng vai "hệ thống" trả lời truy vấn.
• Interactor đọc test input từ stdin (file .in được pipe vào).
• Interactor giao tiếp với thí sinh qua stdin/stdout (pipe hai chiều).
• Interactor trả về exit code: 0 = AC, khác 0 = WA.

Cấu hình bài tương tác

Khi tạo bài trên CTOJ, thiết lập:

• grader = "interactive"
• custom_grader_source = mã nguồn C++ của interactor

Không dùng trường interactive: trong init.yml — nó không có tác dụng. Luôn dùng API.

Viết interactor

Cấu trúc cơ bản

#include <iostream>
#include <string>
using namespace std;

int main() {
    // 1. Đọc dữ liệu test từ stdin
    int x;
    cin >> x;

    // 2. Vòng lặp giao tiếp
    int queries = 0;
    while (true) {
        string cmd;
        if (!(cin >> cmd)) return 1;  // thí sinh ngắt kết nối

        if (cmd == "?") {
            // Xử lý truy vấn
            int y;
            cin >> y;
            queries++;
            if (queries > 30) return 1;  // quá giới hạn

            // Trả lời
            if (y < x) cout << "YES" << endl;
            else cout << "NO" << endl;

        } else if (cmd == "!") {
            // Thí sinh khai báo đáp án
            int ans;
            cin >> ans;
            return (ans == x) ? 0 : 1;  // 0=AC, 1=WA

        } else {
            return 1;  // lệnh không hợp lệ
        }
    }
}

Quy tắc quan trọng

1. Đọc test input từ stdin: File .in được pipe vào stdin của interactor. Đọc bằng cin hoặc scanf bình thường.
2. Giao tiếp với thí sinh qua cin/cout: Sau khi đọc xong test input, mọi cin >> tiếp theo sẽ đọc từ output của thí sinh, và mọi cout << sẽ gửi đến stdin của thí sinh.
3. Flush output: Luôn dùng endl hoặc cout.flush() sau mỗi dòng gửi cho thí sinh.
4. Exit code: return 0 = Accepted, return 1 (hoặc khác 0) = Wrong Answer.
5. Không include testlib.h (trừ khi cần partial scoring): Interactor trên CTOJ dùng plain C++ với exit code.

Xử lý lỗi

Interactor cần xử lý các tình huống bất thường:

// Thí sinh gửi dữ liệu không hợp lệ
int y;
if (!(cin >> y)) return 1;

// Truy vấn ngoài phạm vi
if (y < 1 || y > 1000000000) return 1;

// Quá số truy vấn cho phép
queries++;
if (queries > MAX_QUERIES) return 1;

Viết đề bài tương tác

Đề bài cần mô tả rõ giao thức tương tác:

## Giao thức tương tác

Đây là bài toán **tương tác**. Chương trình giao tiếp với hệ thống qua stdin/stdout.

Bạn có thể thực hiện hai loại thao tác:

- <!--LCODE16-->: Hỏi hệ thống liệu $y < x$. Hệ thống trả lời <!--LCODE17--> hoặc <!--LCODE18-->.
- <!--LCODE19-->: Khai báo đáp án và kết thúc.

Số truy vấn tối đa: $30$.

**Quan trọng:** Sau mỗi lần in, bạn phải flush output:
- C++: <!--LCODE20--> hoặc <!--LCODE21-->
- Python: <!--LCODE22-->

Ví dụ: Lời giải thí sinh

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long lo = 1, hi = 1000000000;
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        cout << "? " << mid << endl;  // flush bằng endl
        string resp;
        cin >> resp;
        if (resp == "YES") lo = mid + 1;
        else hi = mid;
    }
    cout << "! " << lo << endl;
}

Python

lo, hi = 1, 10**9
while lo < hi:
    mid = (lo + hi) // 2
    print(f"? {mid}", flush=True)
    resp = input().strip()
    if resp == "YES":
        lo = mid + 1
    else:
        hi = mid
print(f"! {lo}", flush=True)

File test cho bài tương tác

File .in chứa dữ liệu mà interactor đọc (ví dụ: số ẩn cần tìm). File .out thường để trống hoặc chứa đáp án tham khảo — interactor tự kiểm tra đúng/sai bằng exit code.

# init.yml
archive: tests.zip
testcases:
  - { in: 01.in, out: 01.out, points: 10 }
  - { in: 02.in, out: 02.out, points: 10 }
  ...

Bài mẫu trên CTOJ

• Hidden Integer — bài tương tác mẫu: tìm số ẩn bằng cách hỏi hệ thống tối đa 30 lần.

Lưu ý khi ra đề tương tác

Flush là bắt buộc

Nhắc thí sinh flush output trong đề bài. Nếu không flush, thí sinh sẽ bị TLE vì interactor chờ mãi không nhận được truy vấn.

Giới hạn số truy vấn

Luôn đặt giới hạn rõ ràng cho số truy vấn (ví dụ: $Q\le 30$). Interactor phải kiểm tra và trả WA nếu vượt quá.

Test đầy đủ

Đảm bảo test bao phủ:

• Giá trị nhỏ nhất (ví dụ: $x=1$)
• Giá trị lớn nhất (ví dụ: $x={10}^9$)
• Giá trị ngẫu nhiên
• Trường hợp biên khiến thuật toán sai có thể bị bắt

Lưu interactor trong package

Lưu file interactor tại tests/interactor.cpp trong thư mục bài toán.

Tóm tắt thiết lập