Interactive Problems

Giao thức hỏi và đáp

Lời giải và trình tương tác nối với nhau bằng hai đường ống: những gì lời giải in ra là input của trình tương tác và ngược lại. Một phiên thường gồm:

• Đọc dữ liệu công khai, chẳng hạn $n$.
• Lặp: in một dòng câu hỏi đúng định dạng, đẩy bộ đệm, đọc câu trả lời.
• In dòng kết luận, đẩy bộ đệm, kết thúc.

Đẩy bộ đệm (flush) là bắt buộc: cout gom dữ liệu trong bộ nhớ và chỉ thật sự gửi khi đầy; câu hỏi còn kẹt trong bộ đệm thì trình tương tác không thấy, còn lời giải đứng chờ câu trả lời, hai bên chờ nhau tới hết giờ (thường báo Idleness Limit Exceeded hoặc Time Limit Exceeded). endl vừa xuống dòng vừa đẩy bộ đệm, nên dùng endl cho mọi dòng gửi đi. ios::sync_with_stdio(false) và cin.tie(0) vẫn dùng được, miễn là đẩy bộ đệm đúng lúc.

Khi câu hỏi sai hoặc vượt ngân sách, trình tương tác thường trả $-1$ rồi dừng. Lời giải phải thoát ngay, nếu cứ đọc tiếp có thể nhận một lỗi khó hiểu thay vì Wrong Answer. Gói việc hỏi vào một hàm ask để mọi câu hỏi cùng đi qua một chỗ.

Tự kiểm thử. Đoạn hội thoại mẫu trong đề chỉ là một phiên; không thể dán nó vào input như bài thường. Viết một trình tương tác nhỏ (Python là đủ): sinh trạng thái bí mật ngẫu nhiên, đọc từng dòng của lời giải, kiểm định dạng và ngân sách, trả lời, rồi so kết luận. Chạy vài trăm phiên ngẫu nhiên và vài phiên biên ($n$ nhỏ nhất, phần tử cần tìm ở hai đầu).

Ví dụDãy Sau Những Tổng Đôi

Đề. Dãy ẩn $n$ số nguyên dương, $3 \le n \le 5000$. Câu hỏi ? i j nhận $a_i + a_j$; được hỏi không quá $n$ câu, rồi in ! và cả dãy.

Lời giải. Ba câu $a_1 + a_2$, $a_2 + a_3$, $a_1 + a_3$ cho ba phương trình ba ẩn: $a_1 = \frac{(a_1 + a_2) + (a_1 + a_3) - (a_2 + a_3)}{2}$, rồi suy ra $a_2, a_3$. Mỗi $a_i$ với $i \ge 4$ tốn đúng một câu $a_{i-1} + a_i$. Tổng $3 + (n - 3) = n$ câu, đúng ngân sách. Hỏi các cặp $(1, i)$ cũng được; điều cần là mỗi câu thêm đúng một ẩn mới.

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

ll n, a[5005];

ll ask(ll i, ll j) {
    cout << "? " << i << ' ' << j << endl;
    ll x = -1;
    cin >> x;
    if (x == -1) exit(0);
    return x;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    ll s12 = ask(1, 2), s23 = ask(2, 3), s13 = ask(1, 3);
    a[1] = (s12 + s13 - s23) / 2;
    a[2] = s12 - a[1];
    a[3] = s13 - a[1];
    for (ll i = 4; i <= n; i++) a[i] = ask(i - 1, i) - a[i - 1];
    cout << '!';
    for (ll i = 1; i <= n; i++) cout << ' ' << a[i];
    cout << endl;
}

Câu hỏi phải tách được các khả năng

Trước khi tìm cách hỏi, đếm xem cần phân biệt bao nhiêu khả năng. Câu hỏi có $c$ kiểu trả lời thì $q$ câu phân biệt được tối đa $c^q$ khả năng; cần phân biệt $K$ khả năng thì phải hỏi ít nhất $\lceil \log_c K \rceil$ câu. Câu hỏi có/không ($c = 2$) cho vị trí trong $n = 2 \cdot 10^5$ ô cần ít nhất 18 câu, nên ngân sách 20 câu gợi ý tìm kiếm nhị phân; ngân sách $n$ câu gợi ý mỗi câu chốt một phần tử.

Không phải mọi bài cần chốt hẳn trạng thái. Bài chỉ hỏi một tính chất (nguyên tố hay hợp số, chẵn hay lẻ) thì chỉ cần câu hỏi tách được hai nhóm khả năng, và nhiều khi một danh sách câu hỏi cố định, hỏi mù không cần nhìn câu trả lời trước, là đủ. Khi đó việc chính là chứng minh danh sách ấy tách được mọi trường hợp.

Ví dụPhân Loại Số Bí Mật

Đề. Số bí mật $x$ trong $[2, 100]$. Câu hỏi là một số $q \in [2, 100]$, nhận yes nếu $q$ chia hết $x$. Hỏi không quá 20 câu rồi in prime hoặc composite.

Lời giải. Hỏi 15 số nguyên tố không quá 47 và bốn bình phương $4, 9, 25, 49$, tổng 19 câu; đếm số câu yes. Nếu $x$ là hợp số, viết $x = pq$ với $p \le q$ là hai thừa số, $p$ nguyên tố. Khi $q \ne p$ có một ước nguyên tố khác $p$ không quá $50$, tức không quá 47, nên ít nhất hai số nguyên tố trong danh sách chia hết $x$. Khi $x$ chỉ có một ước nguyên tố $p$ thì $p^2 \mid x$ và $p^2 \le 100$, nên $p \le 7$ và cả $p$ lẫn $p^2$ đều trả yes. Nếu $x$ nguyên tố thì chỉ có thể chính $x$ trả yes. Vậy hợp số khi và chỉ khi có ít nhất hai câu yes; đủ hai thì dừng sớm.

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

ll q[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 4, 9, 25, 49};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll cnt = 0;
    for (ll x : q) {
        cout << x << endl;
        string s;
        cin >> s;
        if (s == "yes") cnt++;
        if (cnt >= 2) break;
    }
    cout << (cnt >= 2 ? "composite" : "prime") << endl;
}

Tìm kiếm nhị phân bằng câu hỏi

Một câu hỏi có/không đơn điệu theo vị trí (sai, sai, …, đúng, đúng) là khuôn của tìm kiếm nhị phân (bài 05): mỗi câu loại một nửa số khả năng, $\lceil \log_2 n \rceil$ câu là đủ. Việc cần làm là biến câu trả lời thành điều kiện đơn điệu. Câu hỏi tổng đoạn cho số bit 1 trên tiền tố, nên số bit 0 trên tiền tố $[1, m]$ là $m$ trừ tổng, tăng theo $m$. Câu hỏi “phần tử lớn thứ hai trong đoạn” cho biết phần tử lớn nhất nằm cùng phía với vị trí đó hay không. Mỗi câu chỉ cần thêm một bit thông tin đúng chỗ.

Ví dụSố Không Thứ K

Đề. Mảng nhị phân ẩn dài $n \le 2 \cdot 10^5$; đọc $n$, $t = 1$, rồi $k$. Câu hỏi ? l r nhận tổng các bit trên $[l, r]$; hỏi không quá 20 câu rồi in ! x, vị trí của số 0 thứ $k$.

Lời giải. Số 0 trong $[1, m]$ là $m - \mathrm{sum}(1, m)$, không giảm theo $m$. Vị trí cần tìm là $m$ nhỏ nhất có ít nhất $k$ số 0 trong $[1, m]$: tìm kiếm nhị phân trên $m$, mỗi bước hỏi ? 1 m. Có $\lceil \log_2 (2 \cdot 10^5) \rceil = 18$ câu.

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

ll n, t, k;

ll ask(ll l, ll r) {
    cout << "? " << l << ' ' << r << endl;
    ll x = -1;
    cin >> x;
    if (x == -1) exit(0);
    return x;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> t >> k;
    ll l = 1, r = n, res = n;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (mid - ask(1, mid) >= k) r = (res = mid) - 1;
        else l = mid + 1;
    }
    cout << "! " << res << endl;
}

Ví dụVị Trí Lớn Nhất

Đề. Mảng ẩn $n \le 10^5$ số khác nhau. Câu hỏi ? l r với $l < r$ nhận chỉ số của phần tử lớn thứ hai trong $[l, r]$. Tìm chỉ số phần tử lớn nhất với không quá 40 câu.

Lời giải. Hỏi cả mảng được $s$, vị trí lớn thứ hai. Một đoạn chứa $s$ trả lời đúng $s$ khi và chỉ khi nó cũng chứa phần tử lớn nhất $p$. Hỏi ? 1 s (khi $s > 1$) để biết $p$ nằm bên trái hay bên phải $s$. Bên trái thì ? m s trả $s$ khi và chỉ khi $m \le p$: tìm $m$ lớn nhất như vậy. Bên phải thì ? s m trả $s$ khi và chỉ khi $m \ge p$: tìm $m$ nhỏ nhất. Tổng $2 + 17 = 19$ câu.

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

ll n;

ll ask(ll l, ll r) {
    cout << "? " << l << ' ' << r << endl;
    ll x = -1;
    cin >> x;
    if (x == -1) exit(0);
    return x;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    ll s = ask(1, n), res;
    if (s > 1 && ask(1, s) == s) {
        ll l = 1, r = s - 1;
        res = 1;
        while (l <= r) {
            ll mid = (l + r) >> 1;
            if (ask(mid, s) == s) l = (res = mid) + 1;
            else r = mid - 1;
        }
    } else {
        ll l = s + 1, r = n;
        res = n;
        while (l <= r) {
            ll mid = (l + r) >> 1;
            if (ask(s, mid) == s) r = (res = mid) - 1;
            else l = mid + 1;
        }
    }
    cout << "! " << res << endl;
}

Hỏi theo cặp để chốt từng phần tử

Khi ngân sách là cỡ $2n$ câu, hãy tìm một cặp câu hỏi mà dù trả lời thế nào cũng chốt chắc một phần tử. Ý quen thuộc là hỏi một quan hệ không đối xứng theo cả hai chiều. Với phép lấy dư trên hai số dương khác nhau $u < v$: $u \bmod v = u$, còn $v \bmod u < u$. Vậy hỏi cả hai chiều, kết quả lớn hơn chính là số nhỏ hơn trong hai số. Duy trì một “ứng viên lớn nhất”, so với từng phần tử mới: số nhỏ hơn của cặp được chốt, số lớn hơn thành ứng viên mới. Ứng viên còn lại cuối cùng là giá trị lớn nhất, suy ra không cần hỏi.

Ví dụHoán Vị Qua Phần Dư

Đề. Hoán vị ẩn $p$ của $1..n$, $n \le 10^4$. Câu hỏi ? i j nhận $p_i \bmod p_j$. Hỏi không quá $2n$ câu rồi in cả hoán vị.

Lời giải. Giữ chỉ số ứng viên mx, ban đầu là 1. Với mỗi $j = 2..n$: hỏi $x = p_{mx} \bmod p_j$ và $y = p_j \bmod p_{mx}$. Nếu $x > y$ thì $p_{mx} = x$ và $j$ thành ứng viên mới; ngược lại $p_j = y$. Cuối cùng $p_{mx} = n$. Tổng $2(n - 1)$ câu; $n = 1$ thì in luôn.

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

ll n, p[10005];

ll ask(ll i, ll j) {
    cout << "? " << i << ' ' << j << endl;
    ll x = -1;
    cin >> x;
    if (x == -1) exit(0);
    return x;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    ll mx = 1;
    for (ll j = 2; j <= n; j++) {
        ll x = ask(mx, j), y = ask(j, mx);
        if (x > y) {
            p[mx] = x;
            mx = j;
        } else p[j] = y;
    }
    p[mx] = n;
    cout << '!';
    for (ll i = 1; i <= n; i++) cout << ' ' << p[i];
    cout << endl;
}