a333. TOI 2024/03 潛力組：營火晚會

題目描述

原有 2N 位島民面向營火圍成一圈，其中 N 人戴白色花冠，N 人戴紅色花冠。離場時，戴白色花冠的人先向左轉，再沿圓圈前進；戴紅色花冠的人則先向右轉，再沿圓圈前進。不同顏色花冠的兩人相遇時，會一起離場。

巧巧戴著額外的一頂白色花冠，可以選擇任意兩位相鄰島民之間加入，共有 2N 個位置可選。加入後白色花冠共有 N+1 頂。請問有多少個加入位置，能讓巧巧一直不遇到紅色花冠的人，成為最後留下的一人？

輸入格式

第一行為整數 N，2 ≤ N ≤ 2×10^5。

第二行為長度 2N 的字串，恰有 N 個 W 與 N 個 R，分別代表白色與紅色花冠。字串表示從某個位置開始，往左方依序看到的花冠顏色。

原題分組限制：30 分：N ≤ 10^3。70 分：無額外限制。

輸出格式

輸出一個正整數，表示能讓巧巧成為最後留下者的加入位置數。

範例 1

輸入：

3
WRRWWR

輸出：

1

範例 2

輸入：

10
WRWRWRWRWRWRWRWRWWRR

輸出：

9

來源

TOI 2024 年 3 月歷屆題〈營火晚會〉，依官方 PDF 重新整理。

官方原題：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202403/CampfireParty.pdf

標籤：TOI 歷屆