C - Vacant Seat Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 500 点

問題文

これはインタラクティブな問題です。

N を 3 以上の奇数とします。

N 個の席が円状に並んでいます。 席には 0 から N - 1 まで番号が振られています。 各 i (0 ≤ i ≤ N - 2) について、席 i と席 i + 1 は隣り合っています。 また、席 N - 1 と席 0 は隣り合っています。

各席の状態は「空席」「男性が座っている」「女性が座っている」のどれかです。 ただし、同性どうしが隣り合う席に座っていることはありません。 N が 3 以上の奇数の場合、空席が少なくとも 1 つは存在することが示せます。

あなたには N のみが与えられ、各席の状態は与えられません。 あなたの目標は、どれか 1 つの空席の番号を当てることです。 そのために、あなたは次のクエリを繰り返し送ることができます。

  • 整数 i (0 ≤ i ≤ N - 1) を選ぶ。 席 i が空席ならば、正答となる。 そうでなければ、席 i に座っている人の性別が知らされる。

クエリを高々 20 回まで送ることで、どれか 1 つの空席の番号を当ててください。

制約

  • N は奇数である。
  • 3 ≤ N ≤ 99,999

入出力

最初に、N が次の形式で標準入力から与えられる。

N

次に、クエリを繰り返し送る。 クエリは次の形式で標準出力へ出力する。 行末には改行を出力せよ。

i

これに対するクエリの答えは、次の形式で標準入力から与えられる。

s

s は Vacant, Male, Female のどれかである。 これらはそれぞれ、席 i の状態が「空席」「男性が座っている」「女性が座っている」であることを表す。

注意

  • 出力の度に標準出力を flush せよ。 そうしない場合、TLE の可能性がある。
  • s が Vacant の場合、すぐにプログラムを終了せよ。 そうしない場合、ジャッジ結果は不定である。
  • クエリ回数が 20 を超えた場合、およびクエリの形式が正しくない場合、ジャッジ結果は不定である。

入出力例 1

このサンプルでは、N = 3 であり、席 0, 1, 2 の状態はそれぞれ「男性が座っている」「女性が座っている」「空席」である。

InputOutput
3
0
Male
1
Female
2
Vacant

Score : 500 points

Problem Statement

This is an interactive task.

Let N be an odd number at least 3.

There are N seats arranged in a circle. The seats are numbered 0 through N-1. For each i (0 ≤ i ≤ N - 2), Seat i and Seat i + 1 are adjacent. Also, Seat N - 1 and Seat 0 are adjacent.

Each seat is either vacant, or oppupied by a man or a woman. However, no two adjacent seats are occupied by two people of the same sex. It can be shown that there is at least one empty seat where N is an odd number at least 3.

You are given N, but the states of the seats are not given. Your objective is to correctly guess the ID number of any one of the empty seats. To do so, you can repeatedly send the following query:

  • Choose an integer i (0 ≤ i ≤ N - 1). If Seat i is empty, the problem is solved. Otherwise, you are notified of the sex of the person in Seat i.

Guess the ID number of an empty seat by sending at most 20 queries.

Constraints

  • N is an odd number.
  • 3 ≤ N ≤ 99 999

Input and Output

First, N is given from Standard Input in the following format:

N

Then, you should send queries. A query should be printed to Standart Output in the following format. Print a newline at the end.

i

The response to the query is given from Standard Input in the following format:

s

Here, s is Vacant, Male or Female. Each of these means that Seat i is empty, occupied by a man and occupied by a woman, respectively.

Notice

  • Flush Standard Output each time you print something. Failure to do so may result in TLE.
  • Immediately terminate the program when s is Vacant. Otherwise, the verdict is indeterminate.
  • The verdict is indeterminate if more than 20 queries or ill-formatted queries are sent.

Sample Input / Output 1

In this sample, N = 3, and Seat 0, 1, 2 are occupied by a man, occupied by a woman and vacant, respectively.

InputOutput
3
0
Male
1
Female
2
Vacant