← 返回题目列表

AtCoder · arc117_c

C. 三色金字塔

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

分数: 600 点

问题陈述

我们有 N 块排列成一排,每个块都被涂成蓝色、白色或红色。 的颜色 i从左边算第一个块 (1 \leq i \leq N) 用一个字符表示 c_i; B, W,和 R 分别代表蓝色、白色和红色。

从这种情况来看,我们将堆叠蓝色、白色和红色块来制作金字塔 N 步骤。下图显示了一个示例:

这里,我们从下到上逐个放置块,如下所示:

  • 如果一个位置正下方的两个方块颜色相同,我们将在该位置放置一个相同颜色的方块;
  • 如果某个位置正下方的两个块具有不同的颜色,我们将在那里放置一个颜色与这两个颜色不同的块。

顶部方块的颜色是什么?

约束

  • N 是满足以下条件的整数 2 \leq N \leq 400000.
  • 每个 c_1, c_2, \dots, c_N is B, W,或 R.

输入

输入由标准输入按以下格式给出:

N
c_1c_2\cdotsc_N

输出

如果最上面的块是蓝色的,则打印 B;如果它是白色的,打印 W;如果它是红色的,则打印 R.


示例输入 1

3
BWR

示例输出 1

W

在这种情况下,我们将按如下方式堆积块:

  • 这 1-st 和 2- 底行左起第2个方块分别是蓝色和白色,所以我们在它上面放置一个红色方块;
  • 这 2-nd 和 3- 底行左起第rd块分别是白色和红色,所以我们在它上面放置一个蓝色块;
  • 中的块 2- 从底部开始的第一行分别是红色和蓝色,因此我们在其顶部放置一个白色块。

因此,顶部的块将是白色的;我们应该打印 W.


示例输入 2

4
RRBB

示例输出 2

W

在这种情况下,我们将按如下方式堆积块:

  • 这 1-st 和 2- 底行左边的第 2 个方块都是红色的,所以我们在它上面放置一个红色方块;
  • 这 2-nd 和 3- 底行左边的第一个方块分别是红色和蓝色,所以我们在它上面放置一个白色方块;
  • 这 3-rd 和 4底行左起第个块都是蓝色的,所以我们在它上面放置一个蓝色块;
  • 这 1-st 和 2- 从左侧开始的第 2 个块 2- 从底部开始的第一行分别是红色和白色,所以我们在它上面放置一个蓝色块;
  • 这 2-nd 和 3- 从左边开始的第一个块 2- 从底部开始的第一行分别是白色和蓝色,所以我们在它上面放置一个红色块;
  • 中的块 3- 从底部开始的第一行分别是蓝色和红色,所以我们在它上面放置一个白色块。

因此,顶部的块将是白色的;我们应该打印 W.


示例输入 3

6
BWWRBW

示例输出 3

B

下图显示了块的最终排列。顶部的方块将是蓝色的;我们应该打印 B.

请注意,这是问题陈述中作为示例显示的情况。


示例输入 4

8
WWBRBBWB

示例输出 4

R

下图显示了块的最终排列。顶部的方块将是红色的;我们应该打印 R.


示例输入 5

21
BWBRRBBRWBRBBBRRBWWWR

示例输出 5

B