← 返回题目列表

Codeforces · 1764/G1

G1. 多蕾米的完美 DS 班 (简易版)

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

这个问题与其他两个版本之间的唯一区别是最大查询数。在此版本中,您最多可以提出 $$$\mathbf{30}$$$ 查询。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

这是一个交互问题。

“大家!多米的完美数据结构课即将开始!如果你想拥有和我一样高的智商,就来加油吧!”今天的数据结构课,Doremy 正在教大家一个强大的数据结构——Doremy 树!现在她给你一个测验来证明你在课堂上专心听讲。

给定一个长度为 $$$m$$$ 的数组 $$$a$$$,Doremy 树支持查询 $$$Q(l,r,k)$$$,其中 $$$1 \leq l \leq r \leq m$$$ 和 $$$1 \leq k \leq m$$$,它返回数组中不同整数的数量$$$\left[\lfloor\frac{a_l}{k} \rfloor, \lfloor\frac{a_{l+1}}{k} \rfloor, \ldots, \lfloor\frac{a_r}{k} \rfloor\right]$$$。

Doremy 有一个从 $$$1$$$ 到 $$$n$$$ 整数的秘密排列 $$$p$$$。您可以进行查询,在一个查询中,给出 $$$3$$$ 整数 $$$l,r,k$$$ ($$$1 \leq l \leq r \leq n$$$, $$$1 \leq k \leq n$$$) 并接收数组 $$$p$$$ 的 $$$Q(l,r,k)$$$ 值。您能否找到索引 $$$y$$$ ($$$1 \leq y \leq n$$$) 使得 $$$p_y=1$$$ 在最多 $$$\mathbf{30}$$$ 查询中?

请注意,在进行任何查询之前,排列 $$$p$$$ 是固定的。

互动

您可以通过读取第一行中的整数 $$$n$$$ ($$$3 \le n \le 1024$$$) 开始交互——排列的长度。

要进行查询,您应该输出

- "? $$$l\ r\ k$$$" ($$$1 \leq l \leq r \leq n$$$, $$$1 \leq k \leq n$$$)

要给出答案,您应该输出

- "!$$$y$$$" ($$$1 \leq y \leq n$$$)

打印查询或答案后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

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

黑客格式

破解的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 1024$$$) — 排列的长度。

攻击的第二行包含 $$$n$$$ 不同的整数 $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i\le n$$$) — 排列。

示例

输入 #1

5

2

2

1

3

输出 #1

? 1 3 4

? 3 5 3

? 3 4 5

? 3 5 2

! 4

注意

示例中的排列为 $$$[3,5,2,1,4]$$$。

例如,输入和输出说明了该测试中可能的交互(插入空行只是为了清楚起见)。

在这个交互过程中:

- 对于第一个查询,$$$\lfloor\frac{3}{4}\rfloor=0,\lfloor\frac{5}{4}\rfloor=1,\lfloor\frac{2}{4}\rfloor=0$$$,所以答案是 $$$2$$$。
- 对于第二个查询,$$$\lfloor\frac{2}{3}\rfloor=0,\lfloor\frac{1}{3}\rfloor=0,\lfloor\frac{4}{3}\rfloor=1$$$,所以答案仍然是$$$2$$$。
- 对于第三个查询,$$$\lfloor\frac{2}{5}\rfloor=0,\lfloor\frac{1}{5}\rfloor=0$$$,所以答案是$$$1$$$。
- 对于第四个查询,$$$\lfloor\frac{2}{2}\rfloor=1,\lfloor\frac{1}{2}\rfloor=0,\lfloor\frac{4}{2}\rfloor=2$$$,所以答案是 $$$3$$$。

经过$$$4$$$查询后得到正确答案,因此判断此过程正确。