← 返回题目列表

AtCoder · abc219_f

I. 清洁机器人

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

广场上有一个清洁机器人 (0, 0) 在无限的二维网格中。

机器人将获得一个由四种字符组成的字符串表示的程序 L, R, U, D.
它将从左到右读取程序中的字符,并对读取的每个字符执行以下操作。

  1. 让 (x, y) 是机器人当前所在的方块。
  2. 根据读取的字符进行以下动作:
    • if L 读取:转到 (x-1, y).
    • if R 读取:转到 (x+1, y).
    • if U 读取:转到 (x, y-1).
    • if D 读取:转到 (x, y+1).

给你一个字符串 S 组成 L, R, U, D。 机器人将执行的程序是以下内容的串联 K 副本 S.

机器人至少访问过一次的方格,包括初始位置 (0, 0),将被清理。
打印程序执行结束时要清理的方块数量。

约束

  • S 是长度介于 1 和 2 \times 10^5 (含)包括 L, R, U, D.
  • 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).


示例输入 2

LR
1000000000000

示例输出 2

2

示例输入 3

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

示例输出 3

219911485785