CF1764G1 Doremy's Perfect DS Class (Easy Version)

本题与其他两个版本的唯一区别在于最多允许的查询次数。在本版本中，你最多可以进行 $ \mathbf{30} $ 次查询。只有当所有版本的问题都被解决后，你才能进行 Hack。 这是一个交互题。 “大家好！Doremy 的完美数据结构课马上开始啦！想要拥有和我一样高的智商就来努力学习吧！”在今天的数据结构课上，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 $），你会收到 $ Q(l,r,k) $ 在排列 $ p $ 上的值。你能否在最多 $ \mathbf{30} $ 次查询内，找出下标 $ y $（$ 1 \leq y \leq n $）使得 $ p_y=1 $？ 注意，排列 $ p $ 在任何查询之前就已经确定。

你开始交互时，首先读取一个整数 $ n $（$ 3 \le n \le 1024 $），表示排列的长度。 每进行一次查询，你应输出 - "? $ l\ r\ k $"（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $） 每行一个。每次查询后，你应读取一个整数 $ x $，即排列 $ p $ 上 $ Q(l,r,k) $ 的值。在本题版本中，你最多可以进行 $ 30 $ 次这样的查询。要给出答案时，你应输出 - "! $ y $"（$ 1 \leq y \leq n $） 每行一个，其中 $ p_y=1 $。每次输出查询或答案后，别忘了输出换行并刷新输出缓冲区，否则会导致 Idleness limit exceeded。具体做法如下： - C++ 使用 fflush(stdout) 或 cout.flush()； - Java 使用 System.out.flush()； - Pascal 使用 flush(output)； - Python 使用 stdout.flush()； - 其他语言请查阅相关文档。 Hack 格式 Hack 的第一行包含一个整数 $ n $（$ 3 \le n \le 1024 $），表示排列的长度。 第二行包含 $ n $ 个互不相同的整数 $ p_1,p_2,\ldots,p_n $（$ 1 \le p_i\le n $），即排列。

见上文输入格式说明。

示例中的排列为 $ [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 $ 次查询后得到了正确答案，因此该过程判为正确。 由 ChatGPT 4.1 翻译