Guess The String

题意翻译

**本题为交互题，使用 IO 交互。** **在你输出一行后，请清空缓冲区：** - 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。 - 在 Pascal 中，使用 `flush(output)`。 - 在 Python 中，使用 `stdout.flush()`。 - 其他语言请自行查阅文档。 **请遵循题目完成交互，发出不合法询问可能会出现 TLE，WA 等问题。** ------------ 给定一个长度为 $n$ 且只包含小写字母的字符串 $S$，你需要猜出它。 一共有 $4$ 种交互方式： | 格式 | 允许调用次数 | 限制 | 返回值 | 说明 | | :----------: | :----------: | :----------: | :----------: | :----------: | | 无 | $1$ | 无 | 一个整数，$n$ 的值。 | **在最开始调用。** | | `? 1 i` | $26$ | $i$ 为 $[1,n]$ 范围内的整数。 | 一个**字符**，$S_i$（$S$ 的第 $i$ 个字符）。 | 无 | | `? 2 l r` | $6 \times 10^3$ | $1 \le l \le r \le n$，且 $l,r$ 为整数。 | 一个整数，$S_{l \ldots r}$（$S$ 的第 $l$ 至 $r$ 个字符）中不同字符的**种数**。 | 无 | | `! s` | $1$ | $s$ 是一个字符串，代表你所认为的 $S$。 | （评测结果——AC 或 WA。） | **最后调用，然后停止交互。** | ------------ 对于 $100\%$ 的数据，$1 \le n \le 10^3$。

题目描述

This is an interactive problem. Remember to flush your output while communicating with the testing program. You may use fflush(stdout) in C++, system.out.flush() in Java, stdout.flush() in Python or flush(output) in Pascal to flush the output. If you use some other programming language, consult its documentation. You may also refer to the guide on interactive problems: <https://codeforces.com/blog/entry/45307>. The jury has chosen a string $ s $ consisting of $ n $ characters; each character of $ s $ is a lowercase Latin letter. Your task is to guess this string; initially, you know only its length. You may ask queries of two types: - $ 1 $ $ i $ — the query of the first type, where $ i $ is an integer from $ 1 $ to $ n $ . In response to this query, the jury will tell you the character $ s_i $ ; - $ 2 $ $ l $ $ r $ — the query of the second type, where $ l $ and $ r $ are integers such that $ 1 \le l \le r \le n $ . In response to this query, the jury will tell you the number of different characters among $ s_l, s_{l+1}, \dots, s_r $ . You are allowed to ask no more than $ 26 $ queries of the first type, and no more than $ 6000 $ queries of the second type. Your task is to restore the string $ s $ . For each test in this problem, the string $ s $ is fixed beforehand, and will be the same for every submission.

输入输出格式

输入格式

Initially, the jury program sends one integer $ n $ on a separate line — the size of $ s $ ( $ 1 \le n \le 1000 $ ).

输出格式

To give the answer, print one line ! s with a line break in the end, where $ s $ should be the string picked by the jury. After that, your program should flush the output and terminate gracefully. Interaction To ask a query, you should send one line containing the query, in one of the following formats: - ? 1 i — for a query of the first type ( $ 1 \le i \le n $ ); - ? 2 l r — for a query of the second type ( $ 1 \le l \le r \le n $ ). Don't forget to flush the output after sending the query line. The answer to your query will be given on a separate line. For a query of the first type, the answer will be the character $ s_i $ . For a query of the second type, the answer will be an integer equal to the number of different characters among $ s_l, s_{l+1}, \dots, s_r $ . You are allowed to ask no more than $ 26 $ queries of the first type, and no more than $ 6000 $ queries of the second type. In case you ask too many queries, or the jury program fails to recognize your query format, the answer to your query will be one integer $ 0 $ . After receiving $ 0 $ as the answer, your program should terminate immediately — otherwise you may receive verdict "Runtime error", "Time limit exceeded" or some other verdict instead of "Wrong answer".

输入输出样例

输入样例 #1

5
4
u
2
g
e
s
1

输出样例 #1

? 2 1 5
? 1 2
? 2 1 2
? 1 1
? 1 3
? 1 4
? 2 4 5
! guess

说明

Let's analyze the example of interaction. The string chosen by the jury is guess, so initially the jury sends one integer $ 5 $ . 1. the first query is ? 2 1 5, which means "count the number of different characters among $ s_1, s_2, \dots, s_5 $ ". The answer to it is $ 4 $ . 2. the second query is ? 1 2, which means "tell which character is $ s_2 $ ". The answer to it is u. 3. the third query is ? 2 1 2, which means "count the number of different characters among $ s_1 $ and $ s_2 $ ". The answer to it is $ 2 $ . 4. the fourth query is ? 1 1, which means "tell which character is $ s_1 $ ". The answer to it is g. 5. the fifth query is ? 1 3, which means "tell which character is $ s_3 $ ". The answer to it is e. 6. the sixth query is ? 1 4, which means "tell which character is $ s_4 $ ". The answer to it is s. 7. the seventh query is ? 2 4 5, which means "count the number of different characters among $ s_4 $ and $ s_5 $ ". The answer to it is $ 1 $ , so it's possible to deduce that $ s_4 $ is the same as $ s_5 $ . In the end, the answer is submitted as ! guess, and it is deduced correctly.

**题目大意：**

这是一个交互式问题。你需要猜测一个由小写拉丁字母组成的字符串 $ s $，其长度为 $ n $。你可以通过两种类型的查询来获取字符串信息：

1. 第一种查询 `? 1 i`，其中 $ i $ 是从 1 到 $ n $ 的整数。响应这种查询时，评委会会告诉你字符 $ s_i $。
2. 第二种查询 `? 2 l r`，其中 $ l $ 和 $ r $ 是满足 $ 1 \le l \le r \le n $ 的整数。响应这种查询时，评委会会告诉你 $ s_l, s_{l+1}, \dots, s_r $ 中不同字符的数量。

你可以进行不超过 26 次的第一种查询，和不超过 6000 次的第二种查询。你的任务是恢复字符串 $ s $。

对于每个测试用例，字符串 $ s $ 是事先固定的，并且对每个提交都相同。

**输入输出数据格式：**

- **输入格式：** 评委会程序首先发送一个整数 $ n $，代表 $ s $ 的大小（$ 1 \le n \le 1000 $）。
- **输出格式：** 为了给出答案，打印一行 `! s`，其中 $ s $ 应该是评委会挑选的字符串。之后，你的程序应该刷新输出并正常终止。

**交互：**

- 要提出查询，你应该发送一行包含以下格式的查询：
- `? 1 i` — 第一种查询（$ 1 \le i \le n $）；
- `? 2 l r` — 第二种查询（$ 1 \le l \le r \le n $）。
- 在发送查询行后，不要忘记刷新输出。
- 你的查询的答案会在单独的一行给出。对于第一种查询，答案将是字符 $ s_i $。对于第二种查询，答案将是一个整数，表示 $ s_l, s_{l+1}, \dots, s_r $ 中不同字符的数量。

如果你提出太多查询，或者评委会程序无法识别你的查询格式，你的查询的答案将是一个整数 0。在收到 0 作为答案后，你的程序应立即终止，否则你可能会收到 "运行错误"、"超出时间限制" 或其他一些判决而不是 "答案错误"。**题目大意：** 这是一个交互式问题。你需要猜测一个由小写拉丁字母组成的字符串 $ s $，其长度为 $ n $。你可以通过两种类型的查询来获取字符串信息： 1. 第一种查询 `? 1 i`，其中 $ i $ 是从 1 到 $ n $ 的整数。响应这种查询时，评委会会告诉你字符 $ s_i $。 2. 第二种查询 `? 2 l r`，其中 $ l $ 和 $ r $ 是满足 $ 1 \le l \le r \le n $ 的整数。响应这种查询时，评委会会告诉你 $ s_l, s_{l+1}, \dots, s_r $ 中不同字符的数量。 你可以进行不超过 26 次的第一种查询，和不超过 6000 次的第二种查询。你的任务是恢复字符串 $ s $。 对于每个测试用例，字符串 $ s $ 是事先固定的，并且对每个提交都相同。 **输入输出数据格式：** - **输入格式：** 评委会程序首先发送一个整数 $ n $，代表 $ s $ 的大小（$ 1 \le n \le 1000 $）。 - **输出格式：** 为了给出答案，打印一行 `! s`，其中 $ s $ 应该是评委会挑选的字符串。之后，你的程序应该刷新输出并正常终止。 **交互：** - 要提出查询，你应该发送一行包含以下格式的查询： - `? 1 i` — 第一种查询（$ 1 \le i \le n $）； - `? 2 l r` — 第二种查询（$ 1 \le l \le r \le n $）。 - 在发送查询行后，不要忘记刷新输出。 - 你的查询的答案会在单独的一行给出。对于第一种查询，答案将是字符 $ s_i $。对于第二种查询，答案将是一个整数，表示 $ s_l, s_{l+1}, \dots, s_r $ 中不同字符的数量。 如果你提出太多查询，或者评委会程序无法识别你的查询格式，你的查询的答案将是一个整数 0。在收到 0 作为答案后，你的程序应立即终止，否则你可能会收到 "运行错误"、"超出时间限制" 或其他一些判决而不是 "答案错误"。