← 返回题目列表

AtCoder · abc421_d

G. RLE 移动

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

分数: 425 点

问题陈述

有一个无限大的网格。网格中的一个单元格称为单元格 (0,0).

单元格位于 r 细胞下降并且 c 单元格右侧的单元格 (0,0) 称为单元格 (r,c).
这里,“r 单元格向下”表示“|r| 细胞向上”时 r 为负,并且“c 单元格右侧“表示”|c| 剩余单元格”时 c 为负。

具体来说,细胞周围的细胞 (0,0) 如下:

Figure

最初,高桥在牢房里 (R_t,C_t) 青木在牢房 (R_a,C_a)。他们每个人都会做出 N 根据字符串移动 S 和 T 长度 N 组成 U, D, L, R.
对于每个 i,高桥和青木的 i-th 次移动同时发生:高桥向上移动一个单元格,如果 i- 第一个字符 S is U,如果 D,如果 L,如果 R;青木的动作也类似 i- 第一个字符 T.

找出高桥和青木在移动后立即位于同一单元格的次数 N 移动。

自从 N 非常大, S 和 T 以以下形式给出 ((S'_1, A_1),\ldots,(S'_M,A_M)) 和 ((T'_1,B_1),\ldots,(T'_L,B_L)),其中 S 是通过连接“得到的字符串A_1 角色副本 S'_1, \dots, A_M 角色副本 S'_M“按此顺序,并且 T 类似地给出。

约束

  • -10^9 \leq R_t,C_t,R_a,C_a \leq 10^9
  • 1\leq N \leq 10^{14}
  • 1\leq M,L \leq 10^5
  • 每个 S'_i 和 T'_i 是其中之一 U, D, L, R.
  • 1 \leq A_i,B_i \leq 10^9
  • A_1+\dots+A_M=B_1+\dots+B_L=N
  • 所有给定值均为整数。

输入

输入由标准输入按以下格式给出:

R_t C_t R_a C_a
N M L
S'_1 A_1
\vdots
S'_M A_M
T'_1 B_1
\vdots
T'_L B_L

输出

打印答案。


示例输入 1

0 0 4 2
3 2 1
R 2
D 1
U 3

示例输出 1

1

在这种情况下, S= RRD 和 T= UUU,动作进行如下:

  • 最初,高桥在牢房里 (0,0) 青木在牢房 (4,2).
  • 之后 1刚搬家,高桥在牢房里 (0,1) 青木在牢房 (3,2).
  • 之后 2第二次搬家,高桥在牢房里 (0,2) 青木在牢房 (2,2).
  • 之后 3rd 移动,高桥在牢房 (1,2) 青木在牢房 (1,2).

因此,高桥和青木在移动后立即位于同一单元格的次数为 1.


示例输入 2

1000000000 1000000000 -1000000000 -1000000000
3000000000 3 3
L 1000000000
U 1000000000
U 1000000000
D 1000000000
R 1000000000
U 1000000000

示例输出 2

1000000001

从 2000000000第 次移动到 3000000000第 次移动,高桥和青木在移动后立即位于同一牢房 1000000001 次。


示例输入 3

3 3 3 2
1 1 1
L 1
R 1

示例输出 3

0

示例输入 4

0 0 0 0
1 1 1
L 1
R 1

示例输出 4

0