P17578 [JAG 2026 Summer Camp #3] Guess Palindrome

Alice has a hidden string $S$ of length $N$ consisting only of the two characters `a` and `b`. Since she likes symmetric strings, it is known that $S$ is a palindrome. Your task is to determine $S$ by asking Alice the following type of query: - You provide an arbitrary non-empty string $T$ of length at most $N$ consisting only of `a` and `b`. - Alice responds with an integer representing the number of occurrences of $T$ as a contiguous substring of $S$. Occurrences are counted even if they overlap. However, to avoid upsetting Alice, you may ask at most $\lfloor N/2\rfloor$ queries. Write a program that determines the hidden string $S$ within the given query limit. ### Interaction First, the length $N$ of $S$ ($2\le N\le100$) is given from standard input. After reading the input, you may start asking queries. To ask a query with a string $T$, print the following format to standard output, where $T$ must be a non-empty string of length at most $N$ consisting only of `a` and `b`. ```text ? T ``` In response to this query, an integer representing the number of occurrences of $T$ as a contiguous substring of $S$ is given from standard input. Once you have determined $S$, print your answer to standard output in the following format. ```text ! S ``` You may ask at most $\lfloor N/2\rfloor$ queries and print the answer exactly once. After printing the answer, your program must terminate immediately. If your program violates the specified format, exceeds the query or answer limit, or produces any extraneous output, your submission will be judged as a wrong answer. Note that you may need to flush the output buffer after each output. Note also that the judge for this problem is not adaptive. The judge determines $S$ before the interaction begins.

N/A

N/A