← 返回题目列表

AtCoder · wtf22_day2_a

A. 帽子拼图

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

你,游戏主持人,以及 N 玩家一起玩一个 戴帽子猜颜色游戏。 玩家依次排队,从前到后编号 1 to N 。

每个玩家戴一顶红色或蓝色的帽子。 帽子的颜色由一个字符串表示 S:玩家 i 戴红帽子,如果 i- 第一个字符 S is R,如果是的话,还有一顶蓝色帽子 B。 你知道这个字符串 S,但是玩家们看不到。每个玩家只能看到前面玩家的帽子颜色(即,编号比自己小的玩家)。特别是,他们看不到自己帽子的颜色。

游戏过程如下。

首先,你数出戴红帽子和蓝帽子的玩家人数,并将其告诉所有玩家。然后,你重复以下事件序列(称为 回合) 10^{100} 次。

  • 你问每个玩家:“你找出自己帽子的颜色了吗?”每个玩家都会诚实回答 Yes or No 但不会被其他玩家听到。
  • 在询问所有玩家之后,你宣布所有已经回答的玩家 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."
  • 圆形 2:
    • 玩家 1:假设他的帽子是蓝色。那么,玩家 2 应该在第 1 轮注意到自己的帽子是红色。然而,玩家 2 实际上回答了 No。因此,他意识到自己的帽子是红色,并回答 Yes 对你的问题的回答。
    • 玩家 2:答案 No 对你的问题的回答。
    • 玩家 3:答案 Yes 对你的问题的回答。
    • 你宣布,“玩家 1 和 3 已回答 Yes."
  • 圆形 3:
    • 玩家 1:答案 Yes 对你的问题的回答。
    • 玩家 2:答案 No 对你的问题的回答。
    • 玩家 3:答案 Yes 对你的问题的回答。
    • 你宣布,“玩家 1 和 3 已回答 Yes."
  • \vdots

经过所有回合后,玩家 1 和 3 知道自己帽子的颜色。 然而,玩家 2 并不知道。 更具体地说,玩家 2 仅凭他所拥有的信息,既不能否定 S=RRB 的可能性,也不能否定 S=RBR 的可能性,所以他无法确定自己帽子的颜色。 因此,应当打印字符串 101 作为答案。