Cleaning Robot

题目描述

有一个清洁机器人位于无限二维格子的方格 $(0, 0)$ 上。 机器人将被赋予一个由四种字符 $L$、$R$、$U$、$D$ 组成的字符串表示的程序。
它会从左到右读取程序中的字符，并对每个读取的字符执行以下操作。

设 $(x, y)$ 为机器人当前所在的方格。 根据读取的字符执行以下移动： 如果读取到 $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$ $K$

输出格式

输出程序执行结束时被清洁的方格数量。

RDRUL
2

7

LR
1000000000000

2

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

219911485785

提示

$S$ 的长度在 $1$ 到 $2 \times 10^5$（含）之间，且由 $L$、$R$、$U$、$D$ 组成。 $1 \leq K \leq 10^{12}$机器人将执行程序 $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)$。

标签: AtCoder|abc219F

来源

AtCoder|abc219F