Aurora Herd Protocol

# Aurora Herd Protocol ## Problem Bessie is guiding a secret herd of Aurora cattle through the Northern Pastures. There are **N** Aurora cattle in the herd, each with a unique herd index from **1** to **N**. One special Aurora cow holds the title of Herd Leader, but her true index is hidden. Your task is to **identify the hidden herd index** by making comparison queries to an interactive judge. ## Interactive Protocol **⚠️ IMPORTANT:** This is an **interactive problem**. It requires a live interactor judge and cannot be solved offline. Do not submit without an active interactor available during judging. ### How It Works The judge has secretly selected a hidden index **X** where **1 ≤ X ≤ N**. Each query allows you to ask: "**Is the hidden index greater than, equal to, or less than value K?**" ### Input/Output Format **First line of input:** - A single integer **N** (1 ≤ N ≤ 10^5) representing the size of the herd. **Your queries:** - Print a query: `? K` where K is an integer you choose. - The judge responds with: - `<` if the hidden index is less than K - `=` if the hidden index equals K - `>` if the hidden index is greater than K **When you know the answer:** - Print `! X` where X is the hidden herd index. - After this line, do not print anything else. Your program must terminate. **Example protocol exchange:** ``` (judge sends) 5 (you query) ? 3 (judge responds) > (you query) ? 4 (judge responds) = (you answer) ! 4 ``` ## Constraints - **N:** 1 ≤ N ≤ 10^5 - **Query limit:** You may make up to ⌊log₂(N)⌋ + 5 queries to account for implementation variations. Queries beyond this limit will cause Wrong Answer. - **Hidden index X:** 1 ≤ X ≤ N ## Sample Interaction See `sample1.in` and `sample1.out` for a transcript-style example showing a successful interaction with **N = 8** and hidden index **5**. ## Notes - The hidden index is fixed before your program starts; it does not change during the interaction. - Use binary search to minimize the number of queries and guarantee a solution within the limit. - After you output `! X`, the judge will terminate your program; you do not need to read further input. - **This problem is currently in draft status and requires an interactor to be functional. Without a proper interactive judge, this problem cannot be executed.**