← 返回题目列表

Codeforces · 399/B

B. 红色和蓝色球

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

用户 ainta 有一堆 n 个红球和蓝球。他可以应用某种操作来改变堆叠内球的颜色。

- 当堆栈顶部的球为红色时,将球从堆栈顶部弹出。
- 然后用红色球替换顶部的蓝色球。
- 最后将一些蓝色球推入堆栈,直到堆栈内总共有 n 个球。

如果堆叠内没有蓝色球,ainta 无法应用此操作。给定堆栈的初始状态,ainta 想知道他可以重复应用的最大操作数。

输入

第一行包含一个整数 n (1 ≤ n ≤ 50) — 堆叠内球的数量。

第二行包含一个字符串 s (|s| = n) 描述堆栈的初始状态。字符串 s 的第 i 个字符表示第 i 个球的颜色(我们将从堆栈的顶部到底部对球进行编号)。如果字符是“R”,则颜色为红色。如果字符是“B”,则颜色为蓝色。

输出

打印可以重复应用的最大操作数。

请不要编写 %lld 说明符来读取或写入 С++ 中的 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

3
RBR

输出 #1

2

输入 #2

4
RBBR

输出 #2

6

输入 #3

5
RBBRR

输出 #3

6

注意

第一个示例如下所示。

用户ainta如何应用第一个操作的说明。他弹出一颗红球,将中间球的颜色从蓝色变为红色,并推入一颗蓝色球。

用户如何应用第二个操作的说明。他不会弹出红球,他只是将顶部球的颜色从蓝色更改为红色。

从现在开始,ainta 无法应用任何操作,因为堆栈内没有蓝色球。 ainta 应用了两次操作,所以答案是 2。

第二个示例如下所示。蓝色箭头表示单个操作。