猜数

题目背景

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

题目描述

珂愛给了你一个 $[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)来解决本题。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

5 5 3

输出样例 #1

3 0

说明

#### 样例解释 你要猜的 $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)。 [样例交互库源代码链接](https://www.luogu.com.cn/paste/uimmq4nj)。**注意,此交互库仅供测试样例使用,实际评测时的交互库此交互库不同**。 如果您不知道如何在本地调试您的代码,请参考[这篇文章](https://www.luogu.com.cn/blog/fusu2333/solution-p1947)。 请特别注意,你的答案应该作为函数的返回值给出,**你不需要,也不应该向标准输出输出任何内容,否则将无法获得分数**。 如果有需要,你可以在选手程序的开头加入一些头文件,当然在本题中这并不是必须的。 交互库给出的函数 `Seniorious` 无法直接调用,需要在选手程序中用 `extern "C"` 关键字声明一次。 下面给出本题的模板程序(请不要使用 gcc9 提交): ```cpp #include <cstdio> // 在本题中并不是必须的 extern "C" int Seniorious(int); // 在这里需要声明一次交互库给出的函数。 extern "C" int Chtholly(int n, int OvO) { // 在这里实现交互库要求你实现的函数。 int ans = 1; for (int l = 1, r = n, mid = (l + r) >> 1; l <= r; mid = (l + r) >> 1) if (Seniorious(mid) >= 0) { r = (ans = mid) - 1; } else { l = mid + 1; } return ans; } ```