AT_apc001_c.Vacant Seat

这是一个交互式问题。

设 $N$ 是一个大于等于 $3$ 的奇数。

有 $N$ 个座位以圆形排列。每个座位编号为 $0$ 到 $N-1$。对于每个 $i$（$0 \leq i \leq N-2$），座位 $i$ 和座位 $i+1$ 相邻。同时，座位 $N-1$ 和座位 $0$ 也是相邻的。

每个座位的状态可能为“空座”、“男性坐在上面”或“女性坐在上面”。但是，不允许有同性别的人坐在相邻座位上。当 $N$ 为大于等于 $3$ 的奇数时，可以证明至少存在一个空座。

你只会被告知 $N$ 的值，并不知道每个座位的具体状态。你的目标是找出任意一个空座的编号。为此，你可以反复进行如下查询：

• 你可以选择一个整数 $i$（$0 \leq i \leq N-1$）。如果第 $i$ 个座位是空座，任务就达成了。如果不是空座，你会被告知这个座位上坐的是男性还是女性。

你最多可以进行 $20$ 次查询，在此之内请找出任意一个空座的编号。

首先，标准输入会给出一个整数 $N$。

$N$

接下来，你可以反复进行查询。每次查询时，请将如下格式输出到标准输出，每次输出后须输出换行并刷新输出缓冲区。

$i$

对于你的查询，会从标准输入返回如下之一：

$s$

$s$ 的值可能是 Vacant、Male 或 Female，分别表示座位 $i$ 的状态为“空座”、“男性坐在上面”或“女性坐在上面”。

输出详见输入格式。找到空座编号 $i$ 后即可结束程序。

限制条件

• $N$ 是奇数。
• $3 \leq N \leq 99,999$

注意事项

• 每次输出后必须刷新输出缓冲区，否则可能会造成“超时”。
• 如果接收到 $s$ 为 Vacant，请立刻终止程序，否则评测结果不确定。
• 如果查询次数超过 $20$ 次，或输出格式错误，评测结果也不确定。

输入输出样例 1

在这个样例中，$N=3$，座位 $0$, $1$, $2$ 的状态分别为“男性坐在上面”、“女性坐在上面”、“空座”。

输入输出示例：

3
0
Male
1
Female
2
Vacant

由 ChatGPT 5 翻译