F - Cleaning Robot Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

無限に広がる二次元グリッドのマス (0, 0) に掃除ロボットが置かれています。

このロボットに、4 種類の文字 L 、R 、U 、D からなる文字列で表されたプログラムが与えられます。
ロボットは、与えられたプログラムの各文字を先頭の文字から順に読み、各文字について以下の行動を行います。

  1. ロボットの現在地をマス (x, y) とする
  2. 読んだ文字に応じて以下の通りに移動する:
    • L を読んだとき: マス (x-1, y) に移動する。
    • R を読んだとき: マス (x+1, y) に移動する。
    • U を読んだとき: マス (x, y-1) に移動する。
    • D を読んだとき: マス (x, y+1) に移動する。

L 、R 、U 、D からなる文字列 S が与えられます。 ロボットが実行するプログラムは、文字列 S を K 個連接したものです。

ロボットが一度でも存在したことのあるマス（ロボットの初期位置であるマス (0, 0) を含む）は掃除されます。
ロボットがプログラムの実行を終えた後の時点で、掃除されているマスの個数を出力して下さい。

制約

  • S は L 、R 、U 、D からなる長さ 1 以上 2 \times 10^5 以下の文字列
  • 1 \leq K \leq 10^{12}

入力

入力は以下の形式で標準入力から与えられる。

S
K

出力

ロボットがプログラムの実行を終えた後の時点で、掃除されているマスの個数を出力せよ。

入力例 1

RDRUL
2

出力例 1

7

ロボットが実行するプログラムは RDRULRDRUL です。ロボットは初期位置であるマス (0, 0) からはじめ、
(0, 0) \rightarrow (1, 0) \rightarrow (1, 1) \rightarrow (2, 1) \rightarrow (2, 0) \rightarrow (1, 0) \rightarrow (2, 0) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 0) \rightarrow (2, 0) と移動します。
その後掃除されているマスは、(0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1) の 7 個です。

入力例 2

LR
1000000000000

出力例 2

2

入力例 3

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

出力例 3

219911485785

Score : 500 points

Problem Statement

There is a cleaning robot on the square (0, 0) in an infinite two-dimensional grid.

The robot will be given a program represented as a string consisting of four kind of characters L, R, U, D.
It will read the characters in the program from left to right and perform the following action for each character read.

  1. Let (x, y) be the square where the robot is currently on.
  2. Make the following move according to the character read:
    • if L is read: go to (x-1, y).
    • if R is read: go to (x+1, y).
    • if U is read: go to (x, y-1).
    • if D is read: go to (x, y+1).

You are given a string S consisting of L, R, U, D. The program that will be executed by the robot is the concatenation of K copies of S.

Squares visited by the robot at least once, including the initial position (0, 0), will be cleaned.
Print the number of squares that will be cleaned at the end of the execution of the program.

Constraints

  • S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of L, R, U, D.
  • 1 \leq K \leq 10^{12}

Input

Input is given from Standard Input in the following format:

S
K

Output

Print the number of squares that will be cleaned at the end of the execution of the program.

Sample Input 1

RDRUL
2

Sample Output 1

7

The robot will execute the program RDRULRDRUL. It will start on (0, 0) and travel as follows:
(0, 0) \rightarrow (1, 0) \rightarrow (1, 1) \rightarrow (2, 1) \rightarrow (2, 0) \rightarrow (1, 0) \rightarrow (2, 0) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 0) \rightarrow (2, 0).
In the end, seven squares will get cleaned: (0, 0), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1).

Sample Input 2

LR
1000000000000

Sample Output 2

2

Sample Input 3

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

Sample Output 3

219911485785