P1947 猜数

这是一道**交互题**。

珂愛给了你一个 $[1,n]$ 之间的整数 $k$，你每次可以询问一个整数 $x$，然后珂愛会告诉你 $x$ 和 $k$ 的大小关系。 你需要用尽可能少的次数猜出珂愛想的数。 你需要实现一个函数 `int Chtholly(int n,int c)`，这个函数的作用是在不超过 $c$ 次询问中猜对 $[1,n]$ 中的一个数，返回值为你最终确定的数。 你可以调用交互库中一个叫做 `Seniorious` 的函数，其原型为 `int Seniorious(int x)`，返回值为： - 若 $k\lt x$，则返回 $1$。 - 若 $k\gt x$，则返回 $-1$。 - 若 $k=x$，则返回 $0$。 你调用 `Seniorious` 函数的次数不超过 $c$ 才能得到这个点的分数，否则这个点为 $0$ 分。有关该函数的调用请参考【说明/提示】部分。 由于珂愛只会写 C++ 语言的交互库，所以你只能使用 C++ 语言（包括 C++，C++11，C++14，C++17，C++20，C++23）来解决本题。

样例输入中三个数分别为 $n,c,k$。这些数据你都**无法读取**。

样例输出中第一个数是你猜的 $k$，第二个数是你调用 `Seniorious` 函数的次数。这些数据你**不必输出**。

#### 样例解释 你要猜的 $k$ 为 $3$。 由于你和珂愛心灵相通，所以在没有调用 `Seniorious` 的情况下就猜出来了。 #### 数据规模与约定 - 对于 $30\%$ 的数据，保证 $c=n-1$。 - 对于 $100\%$ 的数据，保证 $2\leq n\leq 10^6$，$\min(20,n-1)\leq c\leq n$。 #### 提示 [关于交互题](https://help.luogu.com.cn/manual/luogu/problem/interactive-problems)。 样例交互库源代码： ```cpp #include #include int k, cnt; extern "C" { extern int Chtholly(int n, int c); extern int Seniorious(int x) { const int lim = 3000000; if(++cnt > lim) cnt = lim; return (k < x) ? 1 : ((k == x) ? 0 : -1); } } int main() { int n, c; std::cin >> n >> c >> k; int OvO = Chtholly(n, c); std::cout = 0) { r = (ans = mid) - 1; } else { l = mid + 1; } return ans; } ```