Rocket

Created by LXC on Sat Dec 9 10:57:57 2023

https://codeforces.com/problemset/problem/1010/B

ranting: 1800

tag: binary search, interactive

problem

交互题

有一个x，它是属于1到m之间的整数。

每次可向系统询问y。当y < x，则返回1；当y > x，则返回-1；当y = x，则返回0。

但是，系统有时候的返回值是错误的，具体的，当正常返回值为x时，系统返回的为-x。

系统的查询结果正确性是以n为周期的。n不超过30。

现在，要求在不超过60次查询内找出x。

solution

注意到查询x，得到的结果是0。

当我们查询1时，结果系统返回值在正常情况下非0即1。当出现-1则说明这次查询的返回值是错误的。

我们可用前n次查询1，接下来的查询结果是否正常我们都可以知道。

所以剩下的次数可用用二分法求出x。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

vector<int> p = {1, 0, 1, 0, 1, 0};
int x = 10;

int ask(int y, int t) {
    cout << y << endl;
    int rt = 0;
    cin >> rt;
    return rt;
    // if (y > x)
    //     rt = -1;
    // if (y < x)
    //     rt = 1;
    // return p[t % p.size()] ? rt : -rt;
}

void sol() {
    int m, n;
    cin >> m >> n;
    // m = 50, n = 6;
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        int rt = ask(1, i);
        if (rt == 0) {
            return;
        }
        if (rt == 1)
            c[i] = 1;
    }
    int l = 1, r = m + 1;
    for (int i = n; i < 60; i++) {
        int mid = l + r >> 1;
        int rt = ask(mid, i);
        if (rt == 0) {
            return;
        }
        if (!c[i % n]) {
            rt = -rt;
        }
        if (rt == 1) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}