分数: 1000 点
问题陈述
你,游戏主持人,以及 N 玩家一起玩一个 戴帽子猜颜色游戏。 玩家依次排队,从前到后编号 1 to N 。
每个玩家戴一顶红色或蓝色的帽子。
帽子的颜色由一个字符串表示 S:玩家 i 戴红帽子,如果 i- 第一个字符 S is R,如果是的话,还有一顶蓝色帽子 B。
你知道这个字符串 S,但是玩家们看不到。每个玩家只能看到前面玩家的帽子颜色(即,编号比自己小的玩家)。特别是,他们看不到自己帽子的颜色。
游戏过程如下。
首先,你数出戴红帽子和蓝帽子的玩家人数,并将其告诉所有玩家。然后,你重复以下事件序列(称为 回合) 10^{100} 次。
- 你问每个玩家:“你找出自己帽子的颜色了吗?”每个玩家都会诚实回答
YesorNo但不会被其他玩家听到。 - 在询问所有玩家之后,你宣布所有已经回答的玩家
Yes。所有玩家都可以听到这个宣布。请注意,你只宣布玩家编号,而不是他们帽子的颜色。
所有玩家都非常聪明,并且知道其他玩家也同样聪明。他们在第一轮当自己的帽子颜色确定时就开始回答。 Yes 此外,他们知道其他玩家也采取这个策略,并利用这一知识推断自己帽子的颜色。
对每个玩家,找出他们在所有轮次后是否已经知道自己帽子的颜色。
流程 T 每个输入文件的测试用例。
约束
- 1 \leq T \leq 100
- 1 \leq N \leq 100
- S 是一个长度为的字符串 N 组成
R和B. - 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个测试用例 case_i 的格式如下:
N S
输出
对于每个测试用例,将答案打印为一个字符串 N。
的 i-th 个字符应该是 1 如果玩家 i 在所有回合结束后,将发现自己帽子的颜色,并且 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:
- 玩家 1:答案
No对你的问题的回答。 - 玩家 2:答案
No对你的问题的回答。 - 玩家 3:因为他面前的玩家的帽子是红色和蓝色,他意识到自己的帽子是红色。他回答
Yes对你的问题的回答。 - 你宣布,“玩家 3 已回答
Yes."
- 玩家 1:答案
- 圆形 2:
- 玩家 1:假设他的帽子是蓝色。那么,玩家 2 应该在第 1 轮注意到自己的帽子是红色。然而,玩家 2 实际上回答了
No。因此,他意识到自己的帽子是红色,并回答Yes对你的问题的回答。 - 玩家 2:答案
No对你的问题的回答。 - 玩家 3:答案
Yes对你的问题的回答。 - 你宣布,“玩家 1 和 3 已回答
Yes."
- 玩家 1:假设他的帽子是蓝色。那么,玩家 2 应该在第 1 轮注意到自己的帽子是红色。然而,玩家 2 实际上回答了
- 圆形 3:
- 玩家 1:答案
Yes对你的问题的回答。 - 玩家 2:答案
No对你的问题的回答。 - 玩家 3:答案
Yes对你的问题的回答。 - 你宣布,“玩家 1 和 3 已回答
Yes."
- 玩家 1:答案
- \vdots
经过所有回合后,玩家 1 和 3 知道自己帽子的颜色。
然而,玩家 2 并不知道。
更具体地说,玩家 2 仅凭他所拥有的信息,既不能否定 S=RRB 的可能性,也不能否定 S=RBR 的可能性,所以他无法确定自己帽子的颜色。
因此,应当打印字符串 101 作为答案。