「Codeforces 1104D」Game with modulo

发表于 | | 阅读次数:
字数统计: 530 字

Description

题目链接：Codeforces 1104D

这是一道交互题。

Vasya 和 Petya 在玩一个游戏：Petya 有一个正整数 $a$，Vasya 可以询问若干对非负整数 $(x,y)$，对于每次询问，Petya 会回答他：

  • x：如果满足 $x\bmod a\ge y\bmod a$。
  • y：如果满足 $x\bmod a<y\bmod a$。

Vasya 可以询问不超过 $60$ 对数字，保证 $1\le a\le 10^9$。

本题有 $T​$ 组数据。

数据范围：$1\le a\le 10^9$，$1\le T\le 100$

Solution

我们考虑以 $(0,1),(1,2),(2,4),(4,8),\dots,(2^{29},2^{30})$ 这样的方式询问。

显然这样的询问方式中，一定存在 $(l,r)$ 满足 $l<a\le r$。由于 $r=2l<2a$，那么 $l\bmod a\ge r\bmod a$；这意味着 $(l,r)$ 是第一对满足 $x\bmod a\ge y\bmod a$ 的数对 $(x,y)$。

当我们确定了 $(l,r)$，那么我们就确定了 $a$ 的范围 $a\in(l,r]$。于是我们就可以二分 $a$ 的值 $x$。通过询问 $(l,a)$ 很容易得到 $a$ 的值。

最后，我们考虑特殊情况：$a=1$ 或 $a=2$。

  • 当 $a=1$ 时，任何数 $\bmod 1$ 的答案都是 $0$。那么所有的询问对应的答案都应该是 x，特判即可。
  • 当 $a=2$ 时，除了第一组询问答案是 y，其余询问的答案都是 x，特判即可。

时间复杂度：$O(T\log a)$

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
 
#include <cstdio>
#include <algorithm>

char getc() {
    char c=getchar();
    while(c!='x'&&c!='y') c=getchar();
    return c;
}
bool ask(int x,int y) {
    printf("? %d %d\n",x,y),fflush(stdout);
    return getc()=='x';
}
void answer(int x) {
    printf("! %d\n",x),fflush(stdout);
}
int main() {
    char s[10];
    while(~scanf("%s",s)) {
        if(s[0]!='s') break;
        int l=0,r=0,is1,is2;
        ask(0,1)?(is1=1,is2=0):(is1=0,is2=1);
        for(int i=1;i<=30;++i) {
            if(ask(1<<(i-1),1<<i)) !l&&(l=1<<(i-1),r=1<<i);
            else is1=is2=0;
        }
        if(is1) {answer(1);continue;}
        if(is2) {answer(2);continue;}
        int k=l++,ans;
        while(l<=r) {
            int mid=(l+r)>>1;
            if(ask(k,mid)) r=(ans=mid)-1; else l=mid+1;
        }
        answer(ans);
    }
    return 0;
}
0%