A - Hat Puzzle Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

N 人のプレイヤーとゲームマスターのあなたが帽子の色当てゲームをプレイします． プレイヤーは縦一列に並んでおり，前から順に 1 から N までの番号がつけられています．

各プレイヤーは赤または青の帽子をかぶっています． この情報は文字列 S によって表され，S の i 文字目が R ならばプレイヤー i は赤い帽子を，B ならば青い帽子をかぶっています． あなたは文字列 S を知っていますが，プレイヤーは知りません． 各プレイヤーは，自分の前にいるプレイヤー（つまりより番号の小さいプレイヤー）の帽子の色だけを見ることができます． 特に，自分の帽子の色は見えません．

ゲームは次のように進行します．

まずあなたが，赤い帽子をかぶっているプレイヤーの人数と，青い帽子をかぶっているプレイヤーの人数を数え，それを全プレイヤーに伝えます． その後，以下の一連の流れ（ラウンドと呼ぶ）を 10^{100} 回繰り返します．

  • あなたが各プレイヤーに「自分の帽子の色が分かりますか？」と質問する． それに対しプレイヤーは，他のプレイヤーに聞こえないように正直に Yes または No で返答する．
  • すべてのプレイヤーへ質問し終えたら，Yes と答えたプレイヤーを全員発表する． この発表は全プレイヤーが聞くことができる． ただし，発表するのはあくまでプレイヤーの番号であり，その帽子の色は伝えないことに注意せよ．

すべてのプレイヤーはとても賢く，また他のプレイヤーも同様に賢いということを知っています． 彼らは自分の帽子の色が確定した最初のラウンドからあなたの質問に Yes と返答します． また，他のプレイヤーがそのような戦術をとっていることを知った上で，自分の帽子の色を推理します．

各プレイヤーについて，すべてのラウンドが終了した時点で自分の帽子の色が分かっているか否かを求めてください．

1 つの入力ファイルにつき，T 個のテストケースに答えて下さい．

制約

  • 1 \leq T \leq 100
  • 1 \leq N \leq 100
  • S は R と B からなる長さ N の文字列．
  • 入力される値はすべて整数．

入力

入力は以下の形式で標準入力から与えられる．

T
case_1
case_2
\vdots
case_T

各テストケース case_i は以下の形式である．

N
S

出力

各ケースについて，答えを長さ N の文字列として出力せよ． 出力する文字列の i 文字目は，すべてのラウンドが終了した時点でプレイヤー i が自分の帽子の色を知っているなら 1, そうでないなら 0 とせよ．

入力例 1

7
3
RBR
4
BRBR
5
BBBBB
5
BBBRR
20
BRBBRRRRBRRBRBBBRRBR
50
RRBRRRBBBRRRBBBRRBRRBBRBRRBBRRRRRBBBBBRRRBRBRRBRRR
100
BRBRBRBBRRRBBRRBRBBRBBBRBBRBBRRRRBBRRBBBBBBBBBBBBRRBBRBBRBBBBRRRRRRRRRBRBBRBBBBRBBBRBRRBRRBBRBBBBBBB

出力例 1

101
0101
11111
10111
10111111010101011101
11111010111010111010101010101011111111111011111111
1111111001111001111111010001111101011111111011011011111111111111111101111111111111010101011111111111

1 つめのケースでは，ゲームは以下のように進行します．

  • まずあなたが「赤い帽子をかぶっているプレイヤーは 2 人，青い帽子を被っているプレイヤーは 1 人です」と全プレイヤーに伝える．
  • ラウンド 1:
    • プレイヤー 1: あなたの質問に No と返答する．
    • プレイヤー 2: あなたの質問に No と返答する．
    • プレイヤー 3: 前にいるプレイヤーの帽子の色が赤と青なので，自分が赤い帽子をかぶっているとわかる． あなたの質問に Yes と返答する．
    • あなたが「Yes と答えたのはプレイヤー 3 です」と発表する．
  • ラウンド 2:
    • プレイヤー 1: 自分の帽子の色が青だったと仮定する．すると，ラウンド 1 でプレイヤー 2 は自身の帽子の色が赤だと気づいたはずである．しかし実際にはプレイヤー 2 は No と返答している． よって自分の帽子の色は赤だとわかる． あなたの質問に Yes と返答する．
    • プレイヤー 2: あなたの質問に No と返答する．
    • プレイヤー 3: あなたの質問に Yes と返答する．
    • あなたが「Yes と答えたのはプレイヤー 1,3 です」と発表する．
  • ラウンド 3:
    • プレイヤー 1: あなたの質問に Yes と返答する．
    • プレイヤー 2: あなたの質問に No と返答する．
    • プレイヤー 3: あなたの質問に Yes と返答する．
    • あなたが「Yes と答えたのはプレイヤー 1,3 です」と発表する．
  • \vdots

すべてのラウンドが終了した段階で，プレイヤー 1,3 は自分の帽子の色を知っています． しかしプレイヤー 2 はわからないままです． より詳しく言えば，プレイヤー 2 の持つ情報だけでは S=RRB である可能性と S=RBR である可能性がどちらも否定できないため，自分の帽子の色を確定させることができません． よって答えとして文字列 101 を出力します．

Score : 1000 points

Problem Statement

You, the game master, and N players play a Hat Guessing Game. The players line up behind one another, numbered 1 to N from front to back.

Each player wears a red or blue hat. The colors of the hats are represented by a string S: player i wears a red hat if the i-th character of S is R, and a blue hat if it is B. You know the string S, but the players do not. Each player can only see the colors of hats of the players in front of them (namely, the players with smaller player numbers). Particularly, they cannot see the color of their own hat.

The game goes as follows.

First, you count the numbers of players with red hats and those with blue hats, and tell them to all players. Then, you repeat the following sequence of events (called a round) 10^{100} times.

  • You ask each player, "Have you found out the color of your own hat?" Each player will honestly answer Yes or No without being heard by other players.
  • After asking all players, you announce all players who have answered Yes. All players can hear this announcement. Note that you just announce the player numbers and not the colors of their hats.

All players are extremely clever and know that the other players are also clever. They start answering Yes in the first round when the color of their hat is determined. Additionally, they know that the other players also take this strategy, and use this knowledge to infer the color of their hat.

For each player, find whether they will have found out the color of their own hat after all rounds.

Process T test cases for each input file.

Constraints

  • 1 \leq T \leq 100
  • 1 \leq N \leq 100
  • S is a string of length N consisting of R and B.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each test case case_i is in the following format:

N
S

Output

For each test case, print the answer as a string of length N. The i-th character of the string should be 1 if player i will have found out the color of their own hat after all rounds, and 0 otherwise.

Sample Input 1

7
3
RBR
4
BRBR
5
BBBBB
5
BBBRR
20
BRBBRRRRBRRBRBBBRRBR
50
RRBRRRBBBRRRBBBRRBRRBBRBRRBBRRRRRBBBBBRRRBRBRRBRRR
100
BRBRBRBBRRRBBRRBRBBRBBBRBBRBBRRRRBBRRBBBBBBBBBBBBRRBBRBBRBBBBRRRRRRRRRBRBBRBBBBRBBBRBRRBRRBBRBBBBBBB

Sample Output 1

101
0101
11111
10111
10111111010101011101
11111010111010111010101010101011111111111011111111
1111111001111001111111010001111101011111111011011011111111111111111101111111111111010101011111111111

In the first case, the game goes as follows.

  • First, you announce to all players, "Two players wear red hats, and one wears a blue hat."
  • Round 1:
    • Player 1: answers No to your question.
    • Player 2: answers No to your question.
    • Player 3: Because the hats of the players in front of him are red and blue, he realizes his hat is red. He answers Yes to your question.
    • You announce, "Player 3 answered Yes."
  • Round 2:
    • Player 1: Assume his hat is blue. Then, player 2 should have noticed in round 1 that his hat is red. However, player 2 actually answered No. Thus, he realizes his hat is red, and answers Yes to your question.
    • Player 2: answers No to your question.
    • Player 3: answers Yes to your question.
    • You announce, "Players 1 and 3 answered Yes."
  • Round 3:
    • Player 1: answers Yes to your question.
    • Player 2: answers No to your question.
    • Player 3: answers Yes to your question.
    • You announce, "Players 1 and 3 answered Yes."
  • \vdots

After all rounds, players 1 and 3 know the colors of their hats. However, player 2 does not. More specifically, player 2 can deny neither the possibility that S=RRB nor the possibility that S=RBR with just the information he has, so he cannot determine the color of his hat. Thus, the string 101 should be printed as the answer.