Vacant Seat
题意翻译
**这是一道交互题。**
N为3以上的奇数。
有N个座位围成一圈,座位由0到N-1编号,对于每一个座位i(0<=i<=N-2),座位i和i+1是相邻的。座位n-1和0是相邻的。每个座位要么空着,要么坐着男人或女人。没有两个相邻的座位被性别相同的人坐着。可以证明在N为大于3的奇数时至少有一个空位。
给定N,你需要找出一个空位。每次可以询问一个座位i(0<=i<=N-1)的状态,若这个位置是空的,则你通过了这个测试点,否则将会返回位置上人的性别。你要在20次询问内找出一个空座位。
N为奇数,3<=N<=99999
题目描述
[problemUrl]: https://atcoder.jp/contests/apc001/tasks/apc001_c
**これはインタラクティブな問題です。**
$ 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 $ つの空席の番号を当ててください。
### Input & Output Format
最初に、$ N $ が次の形式で標準入力から与えられる。
> $ N $
次に、クエリを繰り返し送る。 クエリは次の形式で標準出力へ出力する。 行末には改行を出力せよ。
> $ i $
これに対するクエリの答えは、次の形式で標準入力から与えられる。
> $ s $
$ s $ は `Vacant`, `Male`, `Female` のどれかである。 これらはそれぞれ、席 $ i $ の状態が「空席」「男性が座っている」「女性が座っている」であることを表す。
输入输出格式
输入格式
输出格式
输入输出样例
暂无测试点说明
### 制約
- $ N $ は奇数である。
- $ 3\ <\ =\ N\ <\ =\ 99,999 $
### 注意
- 出力の度に標準出力を flush せよ。 そうしない場合、`TLE` の可能性がある。
- $ s $ が `Vacant` の場合、すぐにプログラムを終了せよ。 そうしない場合、ジャッジ結果は不定である。
- クエリ回数が $ 20 $ を超えた場合、およびクエリの形式が正しくない場合、ジャッジ結果は不定である。
### 入出力例 1
このサンプルでは、$ N\ =\ 3 $ であり、席 $ 0 $, $ 1 $, $ 2 $ の状態はそれぞれ「男性が座っている」「女性が座っている」「空席」である。
InputOutput30Male1Female2Vacant