← 返回题目列表

Codeforces · 1776/G

G. 另一场品酒活动

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

在第一届成功举办之后,Gabriella 被要求组织第二届品酒活动。会有 $$$2n - 1$$$ 瓶葡萄酒排成一排,每瓶要么是红酒,要么是白葡萄酒。

这次,Gabriella 已经选择了所有瓶子的类型和顺序。葡萄酒的类型由长度为 $$$2n - 1$$$ 的字符串 $$$s$$$ 表示。对于每个 $$$1 \le i \le 2n - 1$$$,如果第 $$$i$$$ 瓶是红酒,则 $$$s_i = \texttt{R}$$$;如果第 $$$i$$$ 瓶是白葡萄酒,则 $$$s_i = \texttt{W}$$$。

正是 $$$n$$$ 评论家被邀请参加。批评者的编号从 $$$1$$$ 到 $$$n$$$。就像去年一样,每个评论家 $$$j$$$ 都想品尝一段葡萄酒,即 $$$a_j, \, a_j + 1, \, \dots, \, b_j$$$ 位置的瓶子,品尝一些 $$$1 \le a_j \le b_j \le 2n - 1$$$。此外,他们还有以下额外要求:

- 他们每个人都想品尝至少$$$n$$$葡萄酒,也就是说,必须满足$$$b_j - a_j + 1 \ge n$$$;
- 没有两个评论家必须品尝完全相同的葡萄酒,也就是说,如果 $$$j \ne k$$$ 则必须持有 $$$a_j \ne a_k$$$ 或 $$$b_j \ne b_k$$$。

加布里埃拉知道,由于赛事在意大利沿海地区举行,评论家对白葡萄酒特别感兴趣,而不太关心红葡萄酒。 (确实,白葡萄酒是海鲜的完美搭配。)因此,为了保证公平,她希望所有评论家品尝相同数量的白葡萄酒。

帮助 Gabriella 找到一个整数 $$$x$$$ ($$$0 \le x \le 2n - 1$$$),这样就存在对评论家的有效区间分配,其中每个评论家都品尝了完全相同的 $$$x$$$ 白葡萄酒。可以证明,至少有一个这样的$$$x$$$总是存在的。

输入

第一行包含整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 其中 $$$2n - 1$$$ 是瓶子数量,$$$n$$$ 是评论家数量。

第二行包含长度为 $$$2n - 1$$$ 的字符串 $$$s$$$,表示葡萄酒的排列 — $$$s$$$ ($$$1 \le i \le 2n - 1$$$) 的第 $$$i$$$ 个字符为 $$$\texttt{R}$$$,对于红酒来说是 $$$\texttt{W}$$$一杯白葡萄酒。

输出

打印一个整数 $$$x$$$ — 每个评论家将品尝的白葡萄酒数量。

可以证明至少存在一个解。如果存在多个解决方案,则其中任何一个都将被接受。

示例

输入 #1

5
RWWRRRWWW

输出 #1

2

输入 #2

1
R

输出 #2

0

注意

在第一个样本中,有 $$$5$$$ 评论家和 $$$2 \cdot 5 - 1 = 9$$$ 瓶葡萄酒。使每个评论家品尝 $$$2$$$ 白葡萄酒的一组可能的间隔如下:$$$[2, 6],$$$ $$$[1, 6],$$$ $$$[4, 8],$$$ $$$[1, 5],$$$ $$$[3, 7]$$$。请注意,所有间隔至少包含 $$$5$$$ 瓶。

在第二个样本中,有 $$$1$$$ 评论家和 $$$2 \cdot 1 - 1 = 1$$$ 瓶葡萄酒。唯一可能的区间是 $$$[1, 1]$$$,它给出 $$$x = 0$$$。