E - Majority of Balls 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点: 800 点

問題文

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

2N 個のボールが一列に並べられており，左から順にボール 1, 2, 3, ..., 2N と番号づけられています．ここで，N は奇数です．この中には，N 個の赤いボールと N 個の青いボールが含まれています．

目隠しをされたあなたは，それぞれのボールの色を当てなければなりません．そのために，以下の質問を 210 回まで行うことができます．

  • 2N 個のボールから任意に N 個を選び，その中で赤いボールと青いボールのどちらの方が多いかを聞く．

では，始めましょう．

制約

  • 1 \leq N \leq 99
  • N は奇数

入出力

最初に，各色のボールの数 N を標準入力から受け取ってください． 

N

次に，すべてのボールの色が分かるまで質問を繰り返してください．
質問は，以下の形式で標準出力に出力してください． 

? A_1 A_2 A_3 ... A_N

これは，あなたが N 個のボール A_1, A_2, A_3, ..., A_N を選んで質問することを意味します．
ただし，1 \leq A_i \leq 2N, A_i \neq A_j (i \neq j) を満たさなければなりません．

これに対する応答は，次の形式で標準入力から与えられます．

T

ここで，T は以下のいずれかの文字列です．

  • Red: 選んだ N 個のボールの中では，青のボールより赤のボールの方が多い．
  • Blue: 選んだ N 個のボールの中では，赤のボールより青のボールの方が多い．
  • -1: あなたは不正な質問 (質問の回数が 210 回を超えた場合を含む)，またはその他の不正な出力を行った．

ジャッジが応答 -1 を返した場合，提出はすでに不正解とみなされています．この場合，プログラムをすぐに終了させてください．

すべてのボールの色が分かったら，解答を以下の形式で標準出力に出力してください． 

! c_1c_2c_3...c_{2N}

ここで，c_i はボール i の色を表す文字で，赤の場合は c_i=R，青の場合は c_i=B としてください．

注意

  • 出力のたびに標準出力を flush してください．そうしない場合、TLE の可能性があります．
  • 解答を出力したら (または応答 -1 を受け取ったら)，プログラムをすぐに終了してください．そうしない場合、ジャッジ結果は不定です。
  • 不正な出力が行われた場合のジャッジ結果は不定です。

入出力例

Input Output
3
? 1 2 3
Red
? 2 4 6
Blue
! RRBBRB

この例では N = 3 であり，ボール 1, 2, 3, 4, 5, 6 の色はそれぞれ赤，赤，青，青，赤，青です．

  • 1 回目の質問では，ボール 1, 2, 3 のうち赤は 2 個，青は 1 個であり，赤の方が多いのでジャッジは Red を返します．
  • 2 回目の質問では，ボール 2, 4, 6 のうち赤は 1 個，青は 2 個であり，青の方が多いのでジャッジは Blue を返します．

Score: 800 points

Problem Statement

This is an interactive task.

We have 2N balls arranged in a row, numbered 1, 2, 3, ..., 2N from left to right, where N is an odd number. Among them, there are N red balls and N blue balls.

While blindfolded, you are challenged to guess the color of every ball correctly, by asking at most 210 questions of the following form:

  • You choose any N of the 2N balls and ask whether there are more red balls than blue balls or not among those N balls.

Now, let us begin.

Constraints

  • 1 \leq N \leq 99
  • N is an odd number.

Input and Output

First, receive the number of balls of each color, N, from Standard Input:

N

Then, ask questions until you find out the color of every ball. A question should be printed to Standard Output in the following format:

? A_1 A_2 A_3 ... A_N

This means that you are asking about the N balls A_1, A_2, A_3, ..., A_N, where 1 \leq A_i \leq 2N and A_i \neq A_j (i \neq j) must hold.

The response T to this question will be given from Standard Input in the following format:

T

Here T is one of the following strings:

  • Red: Among the N balls chosen, there are more red balls than blue balls.
  • Blue: Among the N balls chosen, there are more blue balls than red balls.
  • -1: You printed an invalid question (including the case you asked more than 210 questions), or something else that was invalid.

If the judge returns -1, your submission is already judged as incorrect. The program should immediately quit in this case.

When you find out the color of every ball, print your guess to Standard Output in the following format:

! c_1c_2c_3...c_{2N}

Here c_i should be the character representing the color of Ball i; use R for red and B for blue.

Notice

  • Flush Standard Output each time you print something. Failure to do so may result in TLE.
  • Immediately terminate your program after printing your guess (or receiving the -1 response). Otherwise, the verdict will be indeterminate.
  • If your program prints something invalid, the verdict will be indeterminate.

Sample Input and Output

Input Output
3
? 1 2 3
Red
? 2 4 6
Blue
! RRBBRB

In this sample, N = 3, and the colors of Ball 1, 2, 3, 4, 5, 6 are red, red, blue, blue, red, blue, respectively.

  • In the first question, there are two red balls and one blue ball among the balls 1, 2, 3, so the judge returns Red.
  • In the second question, there are one red ball and two blue balls among the balls 2, 4, 6, so the judge returns Blue.