P1947 Guess the Number

This is an **interactive problem**.

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.

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

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.

#### 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](https://help.luogu.com.cn/manual/luogu/problem/interactive-problems). Sample interactive library source code: ```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; } ``` Translated by ChatGPT 5