题目描述

难度分:$2000$

输入$n(3 \leq n \leq 1000)$。

评测机有一个在$[1,n-1]$中的整数$x$，你需要猜出$x$是多少。

你可以执行如下询问，至多$15$次：

+ c：让评测机把$x$永久增加$c(1 \leq c \leq n-1)$，然后评测机返回给你$\lfloor \frac{x}{n} \rfloor$。

如果你猜出了当前的$x$是多少，那么立刻输出! x。

注意：你需要输出的是$x$增加之后的值，不是初始值。

输入样例$1$

3

1

输出样例$1$

+ 1

! 3

输入样例$2$

5

0

0

1

输出样例$2$

+ 1

+ 1

+ 1

! 5

输入样例$3$

10

0

0

1

2

输出样例$3$

+ 2

+ 2

+ 3

+ 8

! 20

算法

二分答案

这个搜索次数的限制，比较容易想到二分答案，但由于$x$在不断变化，$check$会比较难思考。我们可以二分最初的那个$x=x_0$。并记录下整个搜索过程中累加的总数$tot$，那么最终的答案就应该是$x=x_0+tot$。

记上一次$\lfloor \frac{x}{n} \rfloor$的值为$last$，构造出一个可以产生单调性的增量。可以每次让$tot$增加$c=n-((tot+mid) \% n)$，即尽可能把当前的$x$往其上面的第一个$n$的倍数去凑。如果此时$x=\lfloor \frac{x+c}{n} \rfloor$的值$\gt last$，就抛弃左边一半区间（但有可能是答案），否则抛弃右边一半区间。

最后的答案$x$就是二分出来的$x_0$加上这个过程中的$tot$。

复杂度分析

时间复杂度

比较直观，就是在$[1,n-1]$上进行二分。二分答案的时间复杂度为$O(log_2n)$。

空间复杂度

整个过程仅使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int l = 1, r = n - 1, tot = 0, last = 0;
    while(l < r){
        int mid = l + r + 1 >> 1;
        int c = n - (tot + mid) % n;
        printf("+ %d\n", c);
        fflush(stdout);
        int res;
        scanf("%d", &res);
        if(res > last) {
            l = mid;
        }else {
            r = mid - 1;
        }
        tot += c;
        last = res;
    }
    printf("! %d\n", tot + l);
    fflush(stdout);
    return 0;
}