Bit Guessing Game

发表于 分类于 ，

    交互题

    你需要猜测一个数n，初始时给出n的二进制比特位的1的个数。

    每次查询提供x，必须保证x不大于n，然后更新n为n-x，然后得到查询结果是n的二进制比特位的1的个数。

    请在30次操作内找出n。

Bit Guessing Game

Created by LXC on Mon Sep 18 10:19:17 2023

https://codeforces.com/problemset/problem/1780/D

ranting: 1800

tag: binary search, bitmasks, constructive algorithms, interactive

problem

交互题

你需要猜测一个数n，初始时给出n的二进制比特位的1的个数。

每次查询提供x，必须保证x不大于n，然后更新n为n-x，然后得到查询结果是n的二进制比特位的1的个数。

请在30次操作内找出n。

solution

被折磨了一下午，焯！

通过一个测试用例，我们进行如下构造。

每次减少一个2的幂次，然后发现1的个数增多了，通过增多的1的个数可以确定前方最近的1。

然后删除最近的1到当前位置之间产生的1.

每次消去一个1最多需要两次操作。这样就需要60次操作。

1
2
3
4
5
6
7
8
9
10
100100111
100100110
100100101
100100100
100100011
100100000
100011000
100000000
011100000
000000000

我们是先找最近的1，代价是产生了额外的1，如果我们在找1的过程中顺带把上次产生的额外1消去，这样操作次数会减半。

找规律找了很久，太难调了

1
2
3
4
5
6
100100111
100100110
100100101
100100010
100011100
011100000

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#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;

ll cur = 231232195;

ll cntbit(ll x) {
    ll cnt = 0;
    while (x) {
        cnt += x&1;
        x>>=1;
    }
    return cnt;
}

ll getn(ll x) {
    cur -= x;
    cout << cur << endl;
    return cntbit(cur);
}


void sol() {
    ll n;
    // n = getn(0);
    cin >> n;
    ll b = 0, p = n, d = 0;
    ll ans = 0;
    while (d < n) {
        cout << "- " << (1LL<<b+1) - (1LL<<b-d) << endl;
        p = n;
        // n = getn((1LL<<b+1) - (1LL<<b-d));
        cin >> n;
        if (n == -1) return ;
        d = n-(p-d)+1;
        b += d;
        // cout << "d: " << d << " p: " << p << " n: " << n << " b: " << b << endl;
        ans |= 1<<b;
    }
    cout << "! " << ans << endl;
}

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;
}