← 返回题目列表

AtCoder · apc001_c

C. 空座

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

分数: 500 点

问题陈述

这是一项交互式任务。

让 N 至少为奇数 3.

有 N 座位围成一圈。 座位有编号 0 通过 N-1。 对于每个 i (0 ≤ i ≤ N - 2), 座位 i 和座位 i + 1 相邻。 还有,座位 N - 1 和座位 0 相邻。

每个座位要么空着,要么被男人或女人占据。 然而,相邻的两个座位上没有两个同性别的人占据。 可以证明至少有一个空座位 N 至少是奇数 3.

你被给予 N,但未给出席位的状态。 您的目标是正确猜测任一空座位的 ID 号。 为此,您可以重复发送以下查询:

  • 选择一个整数 i (0 ≤ i ≤ N - 1)。如果座位 i 为空,问题解决。否则,您会收到座位上人员的性别通知 i.

最多发送猜测空座ID号 20 查询。

约束

  • N 是奇数。
  • 3 ≤ N ≤ 99 999

输入和输出

首先, N 由标准输入以以下格式给出:

N

然后,您应该发送查询。 查询应按以下格式打印到标准输出。 在末尾打印换行符。

i

对查询的响应由标准输入以以下格式给出:

s

在这里, s is Vacant, Male or Female。 其中每一个都意味着座位 i 是空的,分别被男人占据和女人占据。

通知

  • 每次打印内容时刷新标准输出。如果不这样做可能会导致 TLE.
  • 立即终止程序 s is Vacant。否则,判决是不确定的。
  • 如果超过 发送了 20 查询或格式错误的查询。

示例输入/输出 1

在此示例中, N = 3和座位 0, 1, 2 分别为男性占用、女性占用和空缺。

输入输出
3
0
男
1
女
2
空缺