题解：P13134 [GCJ 2018 Qualification] Go, Gopher!

seeker142 · 2025-07-25 15:57:59 · 题解

真水的交互蓝题……

吐槽一下：交互题难度虚高，另一个例子：CF1039B

注意到可以每次操作一个 3 \times 3 矩形直至填满。

考虑填满一个 3 \times 3x 的矩形。

然后就过了……

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

bool dig[3][3];

int main() {
    int T;
    cin >> T;
    while (T --) {
        int A;
        cin >> A;
        for (int i = 3; ; i += 3) {
            memset(dig, 0, sizeof(dig));
            for (int cnt = 0; cnt < 9; ) {
                int I = i, J = 3;
                cout << I << ' ' << J << endl;
                cin >> I >> J;
                if (!I && !J) goto end;
                if (I == -1 && J == -1) return 0;
                if (!dig[I - i + 1][J - 2]) ++ cnt;
                dig[I - i + 1][J - 2] = true;
            }
        }
        end:;
    }
    return 0;
}

求一下期望次数：

经典结论：正面概率为 p 的硬币的期望正面次数是 \frac{1}{p}。

所以填满一个 3 \times 3 网格的期望次数为 \frac{9}{9}+\frac{9}{8}+\frac{9}{7}+\ldots+\frac{9}{1} \approx 25.46 \le 25.5。

总期望次数小于填满 \lceil \frac{200}{9} \rceil = 23 次 3 \times 3 网格的期望，所以小于 23 \times 25.5 = 586.5 \ll 1000。