#P1947. 猜数

    ID: 911 Type: RemoteJudge 1000ms 128MiB Tried: 6 Accepted: 6 Difficulty: 2 Uploaded By: Tags>二分答案交互题Special JudgeO2优化

猜数

题目背景

这是一道交互题

题目描述

珂愛给了你一个 [1,n][1,n] 之间的整数 kk,你每次可以询问一个整数 xx,然后珂愛会告诉你 xxkk 的大小关系。

你需要用尽可能少的次数猜出珂愛想的数。

你需要实现一个函数 int Chtholly(int n,int c),这个函数的作用是在不超过 cc 次询问中猜对 [1,n][1,n] 中的一个数,返回值为你最终确定的数。

你可以调用交互库中一个叫做 Seniorious 的函数,其原型为 int Seniorious(int x),返回值为:

  • k<xk\lt x,则返回 11
  • k>xk\gt x,则返回 1-1
  • k=xk=x,则返回 00

你调用 Seniorious 函数的次数不超过 cc 才能得到这个点的分数,否则这个点为 00 分。有关该函数的调用请参考【说明/提示】部分。

由于珂愛只会写 C++ 语言的交互库,所以你只能使用 C++ 语言(包括 C++,C++11,C++14,C++17)来解决本题。

输入格式

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

输出格式

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

5 5 3
3 0

提示

样例解释

你要猜的 kk33

由于你和珂愛心灵相通,所以在没有调用 Seniorious 的情况下就猜出来了。

数据规模与约定

  • 对于 30%30\% 的数据,保证 c=n1c=n-1
  • 对于 100%100\% 的数据,保证 2n1062\leq n\leq 10^6min(20,n1)cn\min(20,n-1)\leq c\leq n

提示

关于交互题

样例交互库源代码链接注意,此交互库仅供测试样例使用,实际评测时的交互库此交互库不同

如果您不知道如何在本地调试您的代码,请参考这篇文章

请特别注意,你的答案应该作为函数的返回值给出,你不需要,也不应该向标准输出输出任何内容,否则将无法获得分数

如果有需要,你可以在选手程序的开头加入一些头文件,当然在本题中这并不是必须的。

交互库给出的函数 Seniorious 无法直接调用,需要在选手程序中用 extern "C" 关键字声明一次。

下面给出本题的模板程序(请不要使用 gcc9 提交):

#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;
}