#P1947. 猜数
猜数
题目背景
这是一道交互题。
题目描述
珂愛给了你一个 之间的整数 ,你每次可以询问一个整数 ,然后珂愛会告诉你 和 的大小关系。
你需要用尽可能少的次数猜出珂愛想的数。
你需要实现一个函数 int Chtholly(int n,int c)
,这个函数的作用是在不超过 次询问中猜对 中的一个数,返回值为你最终确定的数。
你可以调用交互库中一个叫做 Seniorious
的函数,其原型为 int Seniorious(int x)
,返回值为:
- 若 ,则返回 。
- 若 ,则返回 。
- 若 ,则返回 。
你调用 Seniorious
函数的次数不超过 才能得到这个点的分数,否则这个点为 分。有关该函数的调用请参考【说明/提示】部分。
由于珂愛只会写 C++ 语言的交互库,所以你只能使用 C++ 语言(包括 C++,C++11,C++14,C++17)来解决本题。
输入格式
样例输入中三个数分别为 。这些数据你都无法读取。
输出格式
样例输出中第一个数是你猜的 ,第二个数是你调用 Seniorious
函数的次数。这些数据你不必输出。
5 5 3
3 0
提示
样例解释
你要猜的 为 。
由于你和珂愛心灵相通,所以在没有调用 Seniorious
的情况下就猜出来了。
数据规模与约定
- 对于 的数据,保证 。
- 对于 的数据,保证 ,。
提示
样例交互库源代码链接。注意,此交互库仅供测试样例使用,实际评测时的交互库此交互库不同。
如果您不知道如何在本地调试您的代码,请参考这篇文章。
请特别注意,你的答案应该作为函数的返回值给出,你不需要,也不应该向标准输出输出任何内容,否则将无法获得分数。
如果有需要,你可以在选手程序的开头加入一些头文件,当然在本题中这并不是必须的。
交互库给出的函数 Seniorious
无法直接调用,需要在选手程序中用 extern "C"
关键字声明一次。
下面给出本题的模板程序
#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;
}