← 返回题目列表

Codeforces · 1019/B

B. 帽子

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

这是一个交互问题。

Imur Ishakov 决定为喜欢玩著名游戏“帽子”的人们组织一个俱乐部。该俱乐部有 n 个学生参观,其中 n 是偶数。伊穆尔将他们全部排成一圈,并举行抽签将学生分成两两,但出了问题。对参与者进行编号,以便参与者 i 和参与者 i + 1 (1 ≤ i ≤ n - 1) 以及参与者 n 和参与者 1 相邻。每个学生都得到一张带有数字的纸,其中每两个相邻学生的数字正好相差 1。计划是让具有相同数字的学生成对,但事实证明并非所有数字都恰好出现两次。

如您所知,最方便的方法是当对方坐在您对面时向他解释这些话。 Students with numbers i and $$i + \frac{n}{2}$$ sit across each other.伊穆尔想知道是否有两个人坐在一起并给出了相同的数字。帮助他找到这样的人(如果存在的话)。

您可以提出“学生 i 收到了哪个号码?”形式的问题,目标是确定所需的配对是否存在于不超过 60 个问题中。

输入

首先给出偶数 n (2 ≤ n ≤ 100 000) — 学生总数。

您最多可以提出 60 个问题。

输出

要询问有关学生 i (1 ≤ i ≤ n) 的问题,您应该打印 «?我”。然后从标准输出中,您可以读取学生 i 收到的数字 ai (- 109 ≤ ai ≤ 109)。

当您找到所需的对时,您应该打印 «! i»,其中 i 是属于该对 (1 ≤ i ≤ n) 的任何学生。如果你确定这样的对不存在,你应该输出 «! -1»。在这两种情况下,您都应该立即终止该程序。

包含您答案的查询不计入 60 个查询的限制。

请确保在每个命令后刷新标准输出。例如,在C++中使用函数fflush(stdout),在Java中调用System.out.flush(),在Pascal中使用flush(output)和Python语言的stdout.flush()。

黑客攻击

使用以下格式进行黑客攻击:

在第一行中,打印一个偶数 n (2 ≤ n ≤ 100 000) — 学生总数。

在第二行中打印 n 个整数 ai (- 109 ≤ ai ≤ 109),用空格分隔,其中 ai 是给第 i 个学生的数字。任何两个相邻元素(包括 n 和 1)必须相差 1 或 - 1。

被黑客攻击的解决方案将无法直接访问序列 ai。

示例

输入 #1

8
2
2

输出 #1

? 4
? 8
! 4

输入 #2

6
1
2
3
2
1
0

输出 #2

? 1
? 2
? 3
? 4
? 5
? 6
! -1

注意

语句中的输入输出说明了交互示例。

在第一个示例中,所选序列为 1, 2, 1, 2, 3, 4, 3, 2

在第二个示例中,选择序列为 1, 2, 3, 2, 1, 0。