I hate Cleaning Robot

2 secs 1024 MB
first_vil's icon first_vil

問題文

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

このロボットに、44 種類の文字 LRUD からなる文字列で表されたプログラムが与えられます。

ロボットは、与えられたプログラムの各文字を先頭の文字から順に読み、各文字について以下の行動を行います。

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

「文字 CiC_iDiD_i 個連結したもの」という形式で NN 個の文字列 S1,S2,,SNS_1,S_2,\dots,S_N が与えられます。ロボットが実行するプログラムは NN 個の文字列を任意の順序で連結したもののうちいずれかです。

ロボットが一度でも存在したことのあるマス(ロボットの初期位置であるマス (0,0)(0,0) を含む)は掃除されます。

以下の条件を満たすマスがいくつあるか求めてください。

  • 実行されうるプログラム N!N! 通りのうち 11 通り以上において掃除される。

制約

  • NN11 以上 10001000 以下の整数
  • CiC_iLRUD のいずれか
  • DiD_i11 以上 10001000 以下の整数

入力

NN
C1C_1 D1D_1
C2C_2 D2D_2
\vdots
CNC_N DND_N

出力

答えを出力し、最後に改行してください。

サンプル1

入力
2
R 2
D 3
出力
10

S1=S_1= RRS2=S_2= DDD であるため、実行されるプログラムは RRDDD または DDDRR です。

サンプル2

入力
3
D 3
U 6
D 4
出力
14

サンプル3

入力
8
D 4
R 7
U 7
R 9
D 10
R 9
U 6
L 6
出力
616

Submit


Go (1.21)