C/C++教程

cf1103 B. Game with modulo

本文主要是介绍cf1103 B. Game with modulo,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题意:

交互题

有个未知整数 \(a\in[1,1e9]\),每次问两个数 \(x,y\),返回 \(x\pmod a \ge y\pmod a\) 是否成立

在 60 次内猜出 \(a\)

思路:

倍增猜法,长见识了

首先我想到猜 \(x,2x\),若 $\ge $ 说明 \(a\in [1,2x]\),否则 \(a\in [1,x)\cup (2x,1e9)\)

这样每次得到的合法区间还分开的,不知道怎么处理。

既然 \([1,x)\) 这个区间没法确定,那每次都用一个 \(\le a\) 的 \(x\) 来问不就行了!

正解:

先问 \(1,2\),若返回 \(\ge\) 则说明 \(a\in [1,2]\),否则说明 \(a>2\) 并继续;

再问 \(2,4\),返回 \(\ge\) 说明 \(a\in [3,4]\),否则 \(a>4\) 并继续;

再问 \(4,8\),返回 $\ge $ 说明 \(a\in [5,8]\),否则 \(a>8\) 并继续。

以此类推,最后一定在某次询问 \(x,2x\) 后确定 \(a\in[x+1,2x]\) 。但是注意,区间 \([1,2]\) 是特殊情况,不知道怎么处理只好特判一下。

接下来怎么办?二分!

初始 \(l=x+1,r=2x\)

每次问 \(x,mid\),若 $\ge $ 则 \(a\le mid\),于是令 \(r=mid\);否则 \(a>mid\),于是令 \(l=mid+1\)

bool ask(int x, int y) { //是否>=
    cout << "? " << x << ' ' << y << endl;
    char c; cin >> c; return c == 'x';
}
void ans(int x) {
    cout << "! " << x << endl;
}
signed main() {
    string ty; while(cin >> ty, ty != "end") {
        int x = 1; char res;
        while(!ask(x, 2*x)) x *= 2;

        if(x == 1) {
            ans(ask(0,1) ? 1 : 2);
            continue;
        }

        int l = x + (x > 1), r = x * 2;
        while(l < r) {
            int mid = (ll)l + r >> 1;
            if(ask(x, mid)) r = mid; else l = mid + 1;
        }
        ans(l);
    }
}

这篇关于cf1103 B. Game with modulo的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!