← 返回题目列表

Codeforces · 1924/F

F. 反代理出席

中文机器翻译题面 查看原题

这是一个交互问题!

1048576 先生是那些讨厌浪费时间上课的教师之一。他决定今天尝试一些新的方式,而不是以老式的方式出席。

他的班上有 $$$n$$$ 名学生,卷号为 $$$1$$$ 到 $$$n$$$。他知道今天正好有 $$$1$$$ 学生缺席。为了确定谁缺席,他可以向班级提出一些问题。在每个查询中,他可以提供两个整数 $$$l$$$ 和 $$$r$$$ ($$$1\leq l\leq r\leq n$$$),所有卷号在 $$$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$$$ 学生举手。

在前两种情况下,学生被认为是诚实回答,而在后两种情况中,学生被认为是不诚实回答。学生们可以相互决定他们的策略,而1048576先生并不知道。而且,学生们不想引起任何怀疑,同时又想制造很多混乱。所以,他们的策略总是满足以下两个条件——

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

1048576先生对学生的这种行为感到沮丧。因此,他愿意将最多 $$$2$$$ 学生标记为缺席(尽管他知道只有一个)。如果实际缺席的学生是这两者之一,则表示出勤成功。另外,由于课程时间有限,他最多只能提出 $$$\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$$$。

打印答案后,不要忘记输出行尾并刷新输出缓冲区。否则,您将得到超出空闲限制的判决。要刷新缓冲区,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 阅读其他语言的文档。

请注意,此问题的评分器是自适应的,这意味着答案可能会根据您的查询而变化,但始终与约束和先前查询的答案保持一致。

Hacks 的输入格式

此问题的测试用例同时使用非自适应和自适应评分器。您可以使用非自适应评分器进行修改。

输入的第一行包含单个整数 $$$t$$$ ($$$1\leq t\leq 2048$$$)。

每个测试用例的第一行包含三个整数 $$$g$$$、$$$n$$$ 和 $$$x$$$,其中 $$$g=1$$$(标识该测试用例必须使用非自适应评分器),$$$n$$$ ($$$3\leq n\leq 10^5$$$) 代表班级中的学生人数, $$$x$$$ ($$$1\leq x\leq n$$$) 代表缺席学生的学号。您必须确保所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

每个测试用例的第二行包含一个字符串 $$$S$$$ ($$$1\leq\vert S\vert\leq 120, S_i\in \{\texttt{T},\texttt{F}\}$$$)。该字符串表示真值序列的模式。如果$$$S_{(i-1)\bmod \vert S\vert+1}= \texttt{T}$$$,则学生在第$$$i$$$次查询期间将诚实行事,否则他们将不诚实行事。您还必须确保不存在索引 $$$i$$$ 使得 $$$S_{(i-1)\bmod \vert S\vert+1} = S_{i\bmod \vert S\vert+1} = S_{(i+1)\bmod \vert S\vert+1}$$$。

示例

输入 #1

2
5

3

2

1

2

0

1

0

2

0

1

6

6

2

2

0

1

1

0

0

0

1

输出 #1

? 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

#

注意

对于第一个测试用例,卷号为 $$$2$$$ 的学生缺席,真值序列(请参阅 hacks 部分)为 TFFTFTTF。在执行解决方案期间,此测试用例将使用非自适应评分器。

对于第二个测试用例,卷号为 $$$4$$$ 的学生缺席,真值序列为 FFTFTTFT。在执行解决方案期间,在此测试用例中,您的程序将与自适应评分器交互。因此,实际答案可能会有所不同,具体取决于您的查询,但始终与之前查询的响应保持一致。