Hướng dẫn giải bài tập Interactive

Wiki › Bắt đầu

Hướng dẫn giải bài tập Interactive

huunguyen · Last updated 19, Tháng 4, 2026, 22:16

Bài tập interactive (tương tác) là dạng bài đặc biệt trong competitive programming, nơi chương trình của bạn phải "giao tiếp" với máy chấm trong quá trình chạy.

1. Bài tập Interactive là gì?

Khác với bài thông thường (đọc input → xử lý → in output), bài interactive yêu cầu:

Đọc một phần dữ liệu ban đầu
Gửi truy vấn (query) đến máy chấm
Nhận phản hồi từ máy chấm
Lặp lại bước 2-3 cho đến khi tìm ra đáp án
In kết quả cuối cùng

┌─────────────┐         ┌─────────────┐
│  Chương     │ ──?──▶  │   Máy       │
│  trình      │ ◀─────  │   chấm      │
│  của bạn    │ ──!──▶  │ (interactor)│
└─────────────┘         └─────────────┘

2. Flush Output - Điều quan trọng nhất

Vấn đề: Mặc định, output được lưu trong buffer và chỉ gửi đi khi buffer đầy hoặc chương trình kết thúc. Trong bài interactive, nếu không flush, máy chấm sẽ không nhận được query của bạn → deadlock → TLE.

C++

#include <iostream>
using namespace std;

// Cách 1: endl (tự động flush)
cout << "? " << x << endl;

// Cách 2: flush thủ công
cout << "? " << x << "\n";
cout.flush();

// Cách 3: Tắt sync (nhanh hơn nhưng cẩn thận)
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << "? " << x << "\n" << flush;

Python

# Cách 1: flush=True
print(f"? {x}", flush=True)

# Cách 2: import sys
import sys
print(f"? {x}")
sys.stdout.flush()

Java

import java.io.*;

PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
out.println("? " + x);
out.flush();

3. Các dạng bài Interactive phổ biến

3.1. Binary Search (Tìm kiếm nhị phân)

Mẫu: Tìm số $x$ trong $[1, n]$ , mỗi query hỏi so sánh.

int lo = 1, hi = n;
while (lo < hi) {
    int mid = (lo + hi) / 2;
    cout << "? " << mid << endl;
    string resp; cin >> resp;
    if (resp == "<=") hi = mid;
    else lo = mid + 1;
}
cout << "! " << lo << endl;

Số query: $O (\log n)$

3.2. Chia hết (Divisibility)

Mẫu: Tìm số $x$ , query ? y trả lời $x$ có chia hết cho $y$ không.

Chiến lược:

Hỏi các số nguyên tố nhỏ: 2, 3, 5, 7, 11, ...
Hỏi các lũy thừa nguyên tố: 4, 8, 9, 16, ...
Xác định "chữ ký chia hết" của $x$

3.3. Định lý Thặng dư Trung Hoa (CRT)

Mẫu: Tìm số $x$ , query ? y trả lời $x \mod y$ .

Chiến lược:

Hỏi $x \mod p$ cho các số nguyên tố $p_{1}, p_{2}, \dots, p_{k}$
Dùng CRT ghép lại: nếu $\prod p_{i} > n$ thì $x$ duy nhất

// Ghép hai đồng dư bằng CRT
pair<ll, ll> crt2(ll r1, ll m1, ll r2, ll m2) {
    ll g, x, y;
    g = extgcd(m1, m2, x, y);
    ll lcm = m1 / g * m2;
    ll t = (r2 - r1) / g * x % (m2 / g);
    ll ans = ((r1 + m1 * t) % lcm + lcm) % lcm;
    return {ans, lcm};
}

3.4. Khoảng cách Manhattan

Mẫu: Tìm điểm $(x, y)$ trên lưới, query trả lời khoảng cách Manhattan.

Chiến lược:

Query 4 góc: $(1, 1), (n, 1), (1, n), (n, n)$
Giải hệ phương trình để tìm $(x, y)$

4. Xử lý máy chấm "nói dối" (Lie)

Một số bài cho phép máy chấm nói dối tối đa $k$ lần.

Chiến lược với 1 lie:

Hỏi mỗi query 2 lần:
- Nếu 2 câu trả lời giống nhau → tin tưởng
- Nếu khác nhau → hỏi lần 3, dùng đa số (2/3)
Đếm mismatch:
- Với mỗi ứng viên $x$ , đếm số câu trả lời không khớp
- Ứng viên hợp lệ nếu mismatch $\leq k$

int count_mismatch(int x) {
    int cnt = 0;
    for (auto& [q, ans] : queries) {
        bool expected = /* x thỏa query q */;
        if (expected != ans) cnt++;
    }
    return cnt;
}

vector<int> get_candidates() {
    vector<int> cands;
    for (int x = 1; x <= n; x++)
        if (count_mismatch(x) <= k) // k = số lie tối đa
            cands.push_back(x);
    return cands;
}

5. Máy chấm biến hóa (Adaptive)

Máy chấm adaptive không cố định đáp án từ đầu. Sau mỗi query, máy chấm có thể thay đổi đáp án, miễn là vẫn nhất quán với các câu trả lời trước.

Hậu quả:

Bạn không thể dựa vào may mắn
Phải đảm bảo sau tất cả query, chỉ còn duy nhất 1 đáp án khả thi
Máy chấm sẽ luôn chọn đáp án bất lợi nhất cho bạn

Chiến lược:

Chọn query chia đều tập ứng viên
Mục tiêu: minimize(max(nhánh YES, nhánh NO))

int best_query(vector<int>& candidates) {
    int best_y = -1, best_score = INT_MAX;
    for (int y = 2; y <= n; y++) {
        int yes_cnt = 0, no_cnt = 0;
        for (int x : candidates) {
            if (/* x thỏa query y */) yes_cnt++;
            else no_cnt++;
        }
        if (yes_cnt == 0 || no_cnt == 0) continue;
        int score = max(yes_cnt, no_cnt);
        if (score < best_score) {
            best_score = score;
            best_y = y;
        }
    }
    return best_y;
}

6. Template cơ bản

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    auto ask = [&](int y) -> string {
        cout << "? " << y << endl;
        string resp;
        cin >> resp;
        return resp;
    };

    // Thuật toán của bạn ở đây
    // ...

    cout << "! " << answer << endl;
    return 0;
}

7. Debug bài Interactive

Test local: Viết interactor giả để test
In ra stderr: cerr << "debug: " << x << endl; (không ảnh hưởng đến giao tiếp)
Kiểm tra flush: Đảm bảo mọi output đều được flush
Đọc kỹ format: YES/yes, >=/>/<=/<, có newline không?

8. Các bài tập thực hành

Bài	Kỹ thuật	Độ khó
guessnum1	Binary search cơ bản	800
guessnum2	Binary search + 1 lie	1000
guessnum3	Divisibility	1200
guessnum4	Binary search + lie detection	1400
guessnum6	Divisibility + adaptive + lie	1600
guessnum7	CRT	1700

9. Lỗi thường gặp

Lỗi	Nguyên nhân	Cách sửa
TLE	Quên flush	Thêm `endl` hoặc `flush`
WA	Sai format query	Đọc kỹ đề bài
WA	Vượt giới hạn query	Tối ưu thuật toán
RE	Đọc sau khi máy chấm đóng	Kiểm tra điều kiện dừng

10. Tổng kết

Luôn flush sau mỗi query
Đếm số query để không vượt giới hạn
Với adaptive: đảm bảo duy nhất 1 đáp án sau tất cả query
Với lie: dùng mismatch counting hoặc majority voting
Test kỹ trước khi submit

Bình luận

Không có bình luận tại thời điểm này.