A - Meeting on a Number Line Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君と青木君は、数直線上を歩いています。

時刻 0 に、高橋君は座標 X に、青木君は座標 Y にいます。2 人はこれから T 分間、毎分同時に移動します。

高橋君の移動は長さ T の文字列 A で、青木君の移動は長さ T の文字列 B で表されます。A の i 文字目（1 \leq i \leq T）は、高橋君の時刻 i-1 から時刻 i への移動を、B の i 文字目は、青木君の同じ時間帯の移動を表します。各文字の意味は次の通りです。

  • L : 座標が 1 減少する（負の方向に移動する）
  • R : 座標が 1 増加する（正の方向に移動する）
  • S : 移動しない（座標は変わらない）

各整数時刻 i（1 \leq i \leq T）について、時刻 i における 2 人の座標が等しいとき、時刻 i に 出会った といいます。移動の途中ですれ違う場合は出会いに含めず、また時刻 0 も対象に含みません。

T 分の間に 2 人が出会う回数、すなわち、時刻 i における 2 人の座標が等しいような i（1 \leq i \leq T）の個数を求めてください。

制約

  • 1 \leq T \leq 10^6
  • -10^9 \leq X \leq 10^9
  • -10^9 \leq Y \leq 10^9
  • T, X, Y は整数である。
  • A は L, R, S からなる長さ T の文字列である。
  • B は L, R, S からなる長さ T の文字列である。

入力

T X Y
A
B
  • 1 行目には、移動する時間を表す整数 T（分）、高橋君の初期座標を表す整数 X、青木君の初期座標を表す整数 Y が、スペース区切りで与えられる。
  • 2 行目には、高橋君の移動を表す文字列 A が与えられる。
  • 3 行目には、青木君の移動を表す文字列 B が与えられる。

出力

T 分の間に 2 人が出会う回数を、1 行で出力せよ。

入力例 1

4 0 2
RRSS
SSLL

出力例 1

1

入力例 2

2 0 1
RS
LS

出力例 2

0

入力例 3

12 0 3
RRSRLSRSLSRS
SSSLSRSSLRSS

出力例 3

6

入力例 4

30 -10 15
RRSLSLRSSRRRSLSLRSSRRRSLSLRSSR
SLRSRSLLSRSLRSRSLLSRSLRSRSLLSR

出力例 4

0

入力例 5

1 0 0
R
L

出力例 5

0

Score : 266 pts

Problem Statement

Takahashi and Aoki are walking on a number line.

At time 0, Takahashi is at coordinate X and Aoki is at coordinate Y. From now on, the two will move simultaneously every minute for T minutes.

Takahashi's movement is described by a string A of length T, and Aoki's movement is described by a string B of length T. The i-th character of A (1 \leq i \leq T) represents Takahashi's movement from time i-1 to time i, and the i-th character of B represents Aoki's movement during the same time period. The meaning of each character is as follows:

  • L : The coordinate decreases by 1 (move in the negative direction)
  • R : The coordinate increases by 1 (move in the positive direction)
  • S : Stay in place (the coordinate does not change)

For each integer time i (1 \leq i \leq T), if the coordinates of the two people are equal at time i, we say they met at time i. Passing each other during movement does not count as a meeting, and time 0 is also not considered.

Find the number of times the two people meet during the T minutes, that is, the number of i (1 \leq i \leq T) such that the coordinates of the two people are equal at time i.

Constraints

  • 1 \leq T \leq 10^6
  • -10^9 \leq X \leq 10^9
  • -10^9 \leq Y \leq 10^9
  • T, X, Y are integers.
  • A is a string of length T consisting of L, R, S.
  • B is a string of length T consisting of L, R, S.

Input

T X Y
A
B
  • The first line contains the integer T (in minutes) representing the duration of movement, the integer X representing Takahashi's initial coordinate, and the integer Y representing Aoki's initial coordinate, separated by spaces.
  • The second line contains the string A representing Takahashi's movement.
  • The third line contains the string B representing Aoki's movement.

Output

Output the number of times the two people meet during the T minutes, in a single line.

Sample Input 1

4 0 2
RRSS
SSLL

Sample Output 1

1

Sample Input 2

2 0 1
RS
LS

Sample Output 2

0

Sample Input 3

12 0 3
RRSRLSRSLSRS
SSSLSRSSLRSS

Sample Output 3

6

Sample Input 4

30 -10 15
RRSLSLRSSRRRSLSLRSSRRRSLSLRSSR
SLRSRSLLSRSLRSRSLLSRSLRSRSLLSR

Sample Output 4

0

Sample Input 5

1 0 0
R
L

Sample Output 5

0