English · Original
Chinese · Translation
Formal · Original
Two neighboring kingdoms decided to build a wall between them with some gates to enable the citizens to go from one kingdom to another. Each time a citizen passes through a gate, he has to pay one silver coin.
The world can be represented by the first quadrant of a plane and the wall is built along the identity line (i.e. the line with the equation _x_ = _y_). Any point below the wall belongs to the first kingdom while any point above the wall belongs to the second kingdom. There is a gate at any integer point on the line (i.e. at points (0, 0), (1, 1), (2, 2), ...). The wall and the gates do not belong to any of the kingdoms.
Fafa is at the gate at position (0, 0) and he wants to walk around in the two kingdoms. He knows the sequence _S_ of moves he will do. This sequence is a string where each character represents a move. The two possible moves Fafa will do are '_U_' (move one step up, from (_x_, _y_) to (_x_, _y_ + 1)) and '_R_' (move one step right, from (_x_, _y_) to (_x_ + 1, _y_)).
Fafa wants to know the number of silver coins he needs to pay to walk around the two kingdoms following the sequence _S_. Note that if Fafa visits a gate without moving from one kingdom to another, he pays no silver coins. Also assume that he doesn't pay at the gate at point (0, 0), i. e. he is initially on the side he needs.
## Input
The first line of the input contains single integer _n_ (1 ≤ _n_ ≤ 105) — the number of moves in the walking sequence.
The second line contains a string _S_ of length _n_ consisting of the characters '_U_' and '_R_' describing the required moves. Fafa will follow the sequence _S_ in order from left to right.
## Output
On a single line, print one integer representing the number of silver coins Fafa needs to pay at the gates to follow the sequence _S_.
[samples]
## Note
The figure below describes the third sample. The red arrows represent the sequence of moves Fafa will follow. The green gates represent the gates at which Fafa have to pay silver coins.
<center></center>
两个邻国决定在它们之间修建一堵墙，并设置一些门，以便公民可以从一个王国前往另一个王国。每次公民通过一扇门时，必须支付一枚银币。
世界可以用平面的第一象限表示，墙沿着恒等线（即方程为 $x = y$ 的直线）修建。墙下方的任意点属于第一个王国，墙上方的任意点属于第二个王国。在直线上的每个整数点（即点 $(0, 0)$、$(1, 1)$、$(2, 2)$、...）都设有一扇门。墙和门不属于任何王国。
Fafa 位于点 $(0, 0)$ 的门处，他希望在两个王国中漫步。他知道他将执行的移动序列 $S$。该序列是一个字符串，每个字符代表一次移动。Fafa 可能执行的两种移动是 '_U_'（向上移动一步，从 $(x, y)$ 到 $(x, y + 1)$）和 '_R_'（向右移动一步，从 $(x, y)$ 到 $(x + 1, y)$）。
Fafa 希望知道，按照序列 $S$ 漫步时，他需要支付多少枚银币。注意，如果 Fafa 访问了一扇门但没有从一个王国移动到另一个王国，则无需支付银币。同时假设他在点 $(0, 0)$ 的门处不付费，即他初始时已在正确的那一侧。
输入的第一行包含一个整数 $n$ $(1 ≤ n ≤ 10^5)$ —— 行走序列中的移动次数。
第二行包含一个长度为 $n$ 的字符串 $S$，由字符 '_U_' 和 '_R_' 组成，描述所需的移动。Fafa 将按从左到右的顺序遵循序列 $S$。
在一行中，输出一个整数，表示 Fafa 按照序列 $S$ 行走时在门处需要支付的银币数量。
## Input
输入的第一行包含一个整数 $n$ $(1 ≤ n ≤ 10^5)$ —— 行走序列中的移动次数。
第二行包含一个长度为 $n$ 的字符串 $S$，由字符 '_U_' 和 '_R_' 组成，描述所需的移动。Fafa 将按从左到右的顺序遵循序列 $S$。
## Output
在一行中，输出一个整数，表示 Fafa 按照序列 $S$ 行走时在门处需要支付的银币数量。
[samples]
## Note
下图描述了第三个测试用例。红色箭头表示 Fafa 将遵循的移动序列。绿色的门表示 Fafa 需要支付银币的门。
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of moves.
Let $ S = s_1 s_2 \dots s_n $ be a string over $ \{U, R\} $, representing the sequence of moves.
Let $ (x_0, y_0) = (0, 0) $ be the initial position.
For $ i \in \{1, \dots, n\} $, define the position after the $ i $-th move as $ (x_i, y_i) $, where:
- If $ s_i = U $, then $ (x_i, y_i) = (x_{i-1}, y_{i-1} + 1) $,
- If $ s_i = R $, then $ (x_i, y_i) = (x_{i-1} + 1, y_{i-1}) $.
Let $ G = \{ (k, k) \mid k \in \mathbb{Z}_{\geq 0} \} $ be the set of gate points.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ S \in \{U, R\}^n $
**Objective**
Compute the number of silver coins paid, defined as the number of indices $ i \in \{1, \dots, n\} $ such that:
- $ (x_i, y_i) \in G $, and
- $ (x_{i-1}, y_{i-1}) $ and $ (x_i, y_i) $ lie in *different* kingdoms (i.e., one below and one above the line $ x = y $, or vice versa).
Note: A point $ (x, y) $ is in:
- Kingdom 1 if $ x > y $,
- Kingdom 2 if $ x < y $,
- On the wall (gate) if $ x = y $.
Payment occurs **only** when a move crosses from one kingdom to the other *through a gate*.
API Response (JSON)
{
"problem": {
"name": "B. Fafa and the Gates",
"description": {
"content": "Two neighboring kingdoms decided to build a wall between them with some gates to enable the citizens to go from one kingdom to another. Each time a citizen passes through a gate, he has to pay one sil",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF935B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Two neighboring kingdoms decided to build a wall between them with some gates to enable the citizens to go from one kingdom to another. Each time a citizen passes through a gate, he has to pay one sil...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "两个邻国决定在它们之间修建一堵墙，并设置一些门，以便公民可以从一个王国前往另一个王国。每次公民通过一扇门时，必须支付一枚银币。\n\n世界可以用平面的第一象限表示，墙沿着恒等线（即方程为 $x = y$ 的直线）修建。墙下方的任意点属于第一个王国，墙上方的任意点属于第二个王国。在直线上的每个整数点（即点 $(0, 0)$、$(1, 1)$、$(2, 2)$、...）都设有一扇门。墙和门不属于任何王国。...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the number of moves. \nLet $ S = s_1 s_2 \\dots s_n $ be a string over $ \\{U, R\\} $, representing the sequence of moves. \nLet $ (x_0, y_0) = (0, 0) $ be t...",
"is_translate": false,
"language": "Formal"
}
]
}