Description

Ke'ai gives you an integer $k$ in $[1,n]$. Each time, you may ask an integer $x$, and then Ke'ai will tell you the comparison between $x$ and $k$.

You need to guess the number Ke'ai has in mind using as few queries as possible.

You need to implement a function int Chtholly(int n,int c). This function must correctly guess a number in $[1,n]$ within at most $c$ queries, and return the number you finally determine.

You may call a function in the interactive library called Seniorious, whose prototype is int Seniorious(int x). Its return value is:

• If $k\lt x$, it returns $1$.
• If $k\gt x$, it returns $-1$.
• If $k=x$, it returns $0$.

You can get the score for a test point only if the number of times you call Seniorious does not exceed $c$. Otherwise, this test point scores $0$. For how to call this function, please refer to the Hint section.

Since Ke'ai only provides an interactive library in C++, you can only use C++ (including C++, C++11, C++14, C++17, C++20, C++23) to solve this problem.

Input Format

In the sample input, the three numbers are $n,c,k$. You cannot read these data.

Output Format

In the sample output, the first number is the $k$ you guessed, and the second number is how many times you called Seniorious. You do not need to output these data.

5 5 3

3 0

Hint

Sample Explanation

The $k$ you need to guess is $3$.

Because you and Ke'ai understand each other perfectly, you guessed it without calling Seniorious.

Constraints

• For $30\%$ of the data, it is guaranteed that $c=n-1$.
• For $100\%$ of the data, it is guaranteed that $2\leq n\leq 10^6$ and $\min(20,n-1)\leq c\leq n$.

Hint

About interactive problems.

Sample interactive library source code:

#include <cstdio>
#include <iostream>

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 << OvO << ' ' << cnt << std::endl;
  return 0;
}

Note: this interactive library is only for testing the sample. The actual interactive library used in judging is different from this one.

If you do not know how to debug your code locally, please refer to this article.

Please note that your answer should be given as the return value of the function. You do not need to, and must not, output anything to standard output, otherwise you will not get any score.

If needed, you may add some header files at the beginning of your program. Of course, this is not required for this problem.

The function Seniorious provided by the interactive library cannot be called directly. You need to declare it once in your program using the extern "C" keyword.

Below is the template program for this problem (please do not submit with gcc9):

#include <cstdio>                         // Not required for this problem.

extern "C" int Seniorious(int);           // You need to declare the function provided by the interactive library here.

extern "C" int Chtholly(int n, int OvO) { // Implement the required function here.
  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;
}

Translated by ChatGPT 5