链接: https://cses.fi/problemset/task/3273

板块: Interactive Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

有 $n$ 把椅子排成一个圆圈。每把椅子要么是红色，要么是蓝色。椅子编号为 $1, 2,\dots, n$；对于所有 $1 \le i \le n$，椅子 $i$ 与椅子 $i+1$ 相邻。此处椅子 $n+1$ 指的是椅子 $1$。

你的任务是找出两把颜色相同且彼此相邻的椅子。

为此，你可以进行提问：选择一把椅子，评测机将告诉你该椅子的颜色。

输入

这是一个交互题。你的程序将通过标准输入和输出与评测机进行交互。你应当先读取一个整数 $n$：椅子的数量。

在你的回合中，你可以输出以下内容之一：

• ? i，其中 $1 \le i \le n$：询问椅子 $i$ 的颜色。评测机将返回 R 或 B，分别代表红色或蓝色。
• ! i：报告椅子 $i$ 与椅子 $i+1$ 颜色相同。输出此行后你的程序必须终止。

每行输出后都应跟一个换行符。你必须确保每行输出后都刷新缓冲区。

输出

参见上述交互协议。

数据范围

$3 \le n \le 2 \cdot 10^5$，$n$ 为奇数 你最多可以进行 $20$ 次类型为 ? 的提问

样例

5
? 1
R
? 2
B
? 3
B
! 2