311036: CF1924F. Anti-Proxy Attendance

F. Anti-Proxy Attendancetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is an interactive problem!

Mr. 1048576 is one of those faculty who hates wasting his time in taking class attendance. Instead of taking attendance the old-fashioned way, he decided to try out something new today.

There are $n$ students in his class, having roll numbers $1$ to $n$. He knows that exactly $1$ student is absent today. In order to determine who is absent, he can ask some queries to the class. In each query, he can provide two integers $l$ and $r$ ($1\leq l\leq r\leq n$) and all students whose roll numbers are between $l$ and $r$ (inclusive) will raise their hands. He then counts them to determine if the roll number of the absent student lies between these values.

Things seemed fine until his teaching assistant noticed something — the students are dishonest! Some students whose roll numbers lie in the given range may not raise their hands, while some other students whose roll number does not lie in the given range may raise their hands. But the students don't want to raise much suspicion. So, only the following $4$ cases are possible for a particular query $(l,r)$ —

1. True Positive: $r-l+1$ students are present and $r-l+1$ students raised their hands.
2. True Negative: $r-l$ students are present and $r-l$ students raised their hands.
3. False Positive: $r-l$ students are present but $r-l+1$ students raised their hands.
4. False Negative: $r-l+1$ students are present but $r-l$ students raised their hands.

In the first two cases, the students are said to be answering honestly, while in the last two cases, the students are said to be answering dishonestly. The students can mutually decide upon their strategy, not known to Mr. 1048576. Also, the students do not want to raise any suspicion and at the same time, want to create a lot of confusion. So, their strategy always meets the following two conditions —

1. The students will never answer honestly $3$ times in a row.
2. The students will never answer dishonestly $3$ times in a row.

Mr. 1048576 is frustrated by this act of students. So, he is willing to mark at most $2$ students as absent (though he knows that only one is). The attendance is said to be successful if the student who is actually absent is among those two. Also, due to limited class time, he can only ask up to $\lceil\log_{1.116}{n}\rceil-1$ queries (weird numbers but okay). Help him complete a successful attendance.

Interaction

First read a line containing a single integer $t$ ($1\leq t\leq 2048$) denoting the number of independent test cases that you must solve.

For each test case, first read a line containing a single integer $n$ ($3\leq n\leq 10^5$). Then you may ask up to $\lceil\log_{1.116}{n}\rceil-1$ queries.

To ask a query, print a single line in the format "? l r" (without quotes) $(1\leq l\leq r\leq n)$. Then read a single line containing a single integer $x$ ($r-l\leq x\leq r-l+1$) denoting the number of students who raised their hands corresponding to the query.

To mark a student as absent, print a single line in the format "! a" (without quotes) $(1\leq a\leq n)$. Then read a single integer $y$ ($y\in\{0,1\}$). If the student with roll number $a$ was absent, $y=1$, else, $y=0$. Note that this operation does not count as a query but you can do this operation at most $2$ times.

To end a test case, print a single line in the format "#" (without quotes). Then you must continue solving the remaining test cases.

If you ask more queries than allowed or ask an invalid query, you will get the Wrong answer verdict.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

After printing the answers, do not forget to output end of line and flush the output buffer. Otherwise, you will get the verdict Idleness limit exceeded. To flush the buffer, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• Read documentation for other languages.

Note that the grader for this problem is adaptive meaning that the answer may change depending on your queries but will always remain consistent with the constraints and the answer to the previous queries.

Input format for Hacks

The test cases for this problem use both non-adaptive and adaptive graders. You can use the non-adaptive grader for making hacks.

The first line of input contains a single integer $t$ ($1\leq t\leq 2048$).

The first line of each test case contains three integers $g$, $n$ and $x$ where $g=1$ (to identify that this test case must use the non-adaptive grader), $n$ ($3\leq n\leq 10^5$) represents the number of students in the class and $x$ ($1\leq x\leq n$) represents the roll number of the student who is absent. You must ensure that the sum of $n$ over all test cases does not exceed $10^5$.

The second line of each test case contains a single string $S$ ($1\leq\vert S\vert\leq 120, S_i\in \{\texttt{T},\texttt{F}\}$). This string represents the pattern of the truth sequence. If $S_{(i-1)\bmod \vert S\vert+1}= \texttt{T}$, the students will act honestly during the $i$-th query, otherwise they will act dishonestly. You must also ensure that there is no index $i$ such that $S_{(i-1)\bmod \vert S\vert+1} = S_{i\bmod \vert S\vert+1} = S_{(i+1)\bmod \vert S\vert+1}$.

ExampleInput

2
5

3

2

1

2

0

1

0

2

0

1

6

6

2

2

0

1

1

0

0

0

1

Output

? 1 4

? 3 5

? 2 2

? 1 3

? 3 3

? 3 3

! 3

? 2 4

? 4 4

! 2

#

? 1 6

? 1 3

? 4 6

? 1 1

? 3 3

? 5 5

! 3

? 2 2

? 4 4

! 4

#

Note

For the first test case, the student with roll number $2$ is absent and the truth sequence (see section for hacks) is TFFTFTTF. During execution of your solution, this test case will use a non-adaptive grader.

For the second test case, the student with roll number $4$ is absent, and the truth sequence is FFTFTTFT. During the execution of your solution, in this test case your program will interact with an adaptive grader. So, the actual answer might be different depending on your queries but will always remain consistent with the responses to the previous queries.

**题目大意：**

这是一个交互式问题。

Mr. 1048576 是一个不喜欢浪费时间点名的人。他决定尝试一种新的方法。他的班上有 $ n $ 名学生，学号为 1 到 $ n $。他知道**恰好有 1 名学生缺席**。为了确定哪位学生缺席，他可以向班级提出一些问题。在每次查询中，他可以提供两个整数 $ l $ 和 $ r $ ($ 1 \leq l \leq r \leq n $)，然后所有学号在 $ l $ 和 $ r $ 之间（包括 $ l $ 和 $ r $）的学生将举手。他然后计数来确定缺席学生的学号是否在这些值之间。

但是，他的助教发现学生不诚实！一些学号在给定范围内的学生可能不举手，而一些学号不在给定范围内的学生可能举手。但学生不想引起太多怀疑。所以，对于特定的查询 $ (l,r) $，只有以下 4 种情况是可能的：

1. 真正阳性：$ r-l+1 $ 名学生出席，并且 $ r-l+1 $ 名学生举手。
2. 真正阴性：$ r-l $ 名学生出席，并且 $ r-l $ 名学生举手。
3. 假阳性：$ r-l $ 名学生出席，但是 $ r-l+1 $ 名学生举手。
4. 假阴性：$ r-l+1 $ 名学生出席，但是 $ r-l $ 名学生举手。

在前两种情况下，学生被认为是诚实地回答，而在后两种情况下，学生被认为是撒谎。学生可以相互决定他们的策略，Mr. 1048576 不会知道。同时，学生既不想引起任何怀疑，又想制造很多混乱。所以，他们的策略总是满足以下两个条件：

1. 学生永远不会连续 3 次诚实回答。
2. 学生永远不会连续 3 次不诚实回答。

由于课堂时间有限，他最多只能问 $ \lceil\log_{1.116}{n}\rceil-1 $ 个问题（奇怪的数量，但可以接受）。帮助他成功完成点名。

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

- 输入：
- 第一行包含一个整数 $ t $ ($ 1 \leq t \leq 2048 $)，表示需要解决的独立测试用例的数量。
- 每个测试用例的第一行包含一个整数 $ n $ ($ 3 \leq n \leq 10^5 $)。
- 之后可以进行最多 $ \lceil\log_{1.116}{n}\rceil-1 $ 次查询。

- 查询格式：
- 输出一行，格式为 `? l r` ($ 1 \leq l \leq r \leq n $)。
- 读取一行，包含一个整数 $ x $ ($ r-l \leq x \leq r-l+1 $)，表示对应查询举手的学生数量。

- 标记缺席学生格式：
- 输出一行，格式为 `! a` ($ 1 \leq a \leq n $)。
- 读取一个整数 $ y $ ($ y \in \{0,1\} $)。如果学号为 $ a $ 的学生缺席，则 $ y=1 $，否则 $ y=0 $。注意，这个操作不计入查询次数，但最多可以进行 2 次。

- 结束测试用例：
- 输出一行，格式为 `#`。

- 输出：
- 对于每个测试用例，按照上述格式进行查询和标记，直到成功确定缺席的学生，然后输出 `#` 结束该测试用例。

如果查询次数超过限制或提出无效查询，将得到 **错误答案** 的结果。确保所有测试用例的 $ n $ 之和不超过 $ 10^5 $。

在打印答案后，不要忘记输出换行符并刷新输出缓冲区，否则将得到 **空闲超时** 的结果。**题目大意：** 这是一个交互式问题。 Mr. 1048576 是一个不喜欢浪费时间点名的人。他决定尝试一种新的方法。他的班上有 $ n $ 名学生，学号为 1 到 $ n $。他知道**恰好有 1 名学生缺席**。为了确定哪位学生缺席，他可以向班级提出一些问题。在每次查询中，他可以提供两个整数 $ l $ 和 $ r $ ($ 1 \leq l \leq r \leq n $)，然后所有学号在 $ l $ 和 $ r $ 之间（包括 $ l $ 和 $ r $）的学生将举手。他然后计数来确定缺席学生的学号是否在这些值之间。 但是，他的助教发现学生不诚实！一些学号在给定范围内的学生可能不举手，而一些学号不在给定范围内的学生可能举手。但学生不想引起太多怀疑。所以，对于特定的查询 $ (l,r) $，只有以下 4 种情况是可能的： 1. 真正阳性：$ r-l+1 $ 名学生出席，并且 $ r-l+1 $ 名学生举手。 2. 真正阴性：$ r-l $ 名学生出席，并且 $ r-l $ 名学生举手。 3. 假阳性：$ r-l $ 名学生出席，但是 $ r-l+1 $ 名学生举手。 4. 假阴性：$ r-l+1 $ 名学生出席，但是 $ r-l $ 名学生举手。 在前两种情况下，学生被认为是诚实地回答，而在后两种情况下，学生被认为是撒谎。学生可以相互决定他们的策略，Mr. 1048576 不会知道。同时，学生既不想引起任何怀疑，又想制造很多混乱。所以，他们的策略总是满足以下两个条件： 1. 学生永远不会连续 3 次诚实回答。 2. 学生永远不会连续 3 次不诚实回答。 由于课堂时间有限，他最多只能问 $ \lceil\log_{1.116}{n}\rceil-1 $ 个问题（奇怪的数量，但可以接受）。帮助他成功完成点名。 **输入输出数据格式：** - 输入： - 第一行包含一个整数 $ t $ ($ 1 \leq t \leq 2048 $)，表示需要解决的独立测试用例的数量。 - 每个测试用例的第一行包含一个整数 $ n $ ($ 3 \leq n \leq 10^5 $)。 - 之后可以进行最多 $ \lceil\log_{1.116}{n}\rceil-1 $ 次查询。 - 查询格式： - 输出一行，格式为 `? l r` ($ 1 \leq l \leq r \leq n $)。 - 读取一行，包含一个整数 $ x $ ($ r-l \leq x \leq r-l+1 $)，表示对应查询举手的学生数量。 - 标记缺席学生格式： - 输出一行，格式为 `! a` ($ 1 \leq a \leq n $)。 - 读取一个整数 $ y $ ($ y \in \{0,1\} $)。如果学号为 $ a $ 的学生缺席，则 $ y=1 $，否则 $ y=0 $。注意，这个操作不计入查询次数，但最多可以进行 2 次。 - 结束测试用例： - 输出一行，格式为 `#`。 - 输出： - 对于每个测试用例，按照上述格式进行查询和标记，直到成功确定缺席的学生，然后输出 `#` 结束该测试用例。 如果查询次数超过限制或提出无效查询，将得到 **错误答案** 的结果。确保所有测试用例的 $ n $ 之和不超过 $ 10^5 $。 在打印答案后，不要忘记输出换行符并刷新输出缓冲区，否则将得到 **空闲超时** 的结果。