問題一覧 > 通常問題

No.2716 Falcon Method

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 95
作問者 : ecottea / テスター : 👑 p-adic hamamu
1 ProblemId : 10596 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-02-08 21:48:13

問題文

D，R のみからなる長さ NN の文字列 S=S0S1⋯SN−1S = S_0 S_1 \cdots S_{N-1} が与えられます（添字が 00 始まりであることに注意してください）．

二次元グリッド上を移動する手続き F(h,w,p)F(h, w, p) を以下のように定めます：

  1. 位置を (0,0)(0, 0)，カウンタの値を pp で初期化する．
  2. 現在の位置が (x,y)(x, y)，カウンタの値が ii であるとき，
    • x=hx = h かつ y=wy = w である場合，手続きを終了する．
    • そうでなく x=hx = h である場合，位置を (x,y+1)(x, y + 1) に更新して 2. に戻る．
    • そうでなく y=wy = w である場合，位置を (x+1,y)(x + 1, y) に更新して 2. に戻る．
    • そうでない場合， mod \bmod を剰余を表す二項演算子として，
      • Si=S_i= D ならば位置を (x+1,y)(x + 1, y) に，カウンタを (i+1) mod N(i + 1) \bmod N にそれぞれ更新して 2. に戻る．
      • Si=S_i= R ならば位置を (x,y+1)(x, y + 1) に，カウンタを (i+1) mod N(i + 1) \bmod N にそれぞれ更新して 2. に戻る．

QQ 個のクエリが与えられます．ii 番目のクエリは整数の組 (Hi,Wi,Pi)(H_i, W_i, P_i) で表されるので，手続き F(Hi,Wi,Pi)F(H_i, W_i, P_i) を終えた後のカウンタの値を求めてください．

制約

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤Q≤1051 \leq Q \leq 10^5
  • 1≤Hi,Wi≤1091 \leq H_i, W_i \leq 10^9
  • 0≤Pi<N0 \leq P_i < N
  • SS は D，R のみからなる長さ NN の文字列
  • 入力される数値は全て整数

入力

入力は以下の形式で標準入力から与えられます．

N QN \ Q
SS
H1 W1 P1H_1 \ W_1 \ P_1
⋮\vdots
HQ WQ PQH_Q \ W_Q \ P_Q

出力

QQ 行出力してください．ii 行目には手続き F(Hi,Wi,Pi)F(H_i, W_i, P_i) を終えた後のカウンタの値を出力してください．
最後に改行してください．

サンプル

サンプル1
入力
4 3
RDDR
3 2 1
1 7 0
4 1 3
出力
1
2
0

11 番目のクエリは (3,2,1)(3, 2, 1) であり，手続き F(3,2,1)F(3, 2, 1) は次のように進行します：

  • 位置を (0,0)(0, 0)，カウンタの値を 11 で初期化する．
  • 0<3,0<20 < 3, 0 < 2 で S1=S_1= D なので，位置を (0+1,0)=(1,0)(0+1, 0)=(1, 0)，カウンタの値を (1+1) mod 4=2(1+1) \bmod 4 = 2 に更新する．
  • 1<3,0<21 < 3, 0 < 2 で S2=S_2= D なので，位置を (1+1,0)=(2,0)(1+1, 0)=(2, 0)，カウンタの値を (2+1) mod 4=3(2+1) \bmod 4 = 3 に更新する．
  • 2<3,0<22 < 3, 0 < 2 で S3=S_3= R なので，位置を (2,0+1)=(2,1)(2, 0+1)=(2, 1)，カウンタの値を (3+1) mod 4=0(3+1) \bmod 4 = 0 に更新する．
  • 2<3,1<22 < 3, 1 < 2 で S0=S_0= R なので，位置を (2,1+1)=(2,2)(2, 1+1)=(2, 2)，カウンタの値を (0+1) mod 4=1(0+1) \bmod 4 = 1 に更新する．
  • 2<3,2=22 < 3, 2 = 2 なので，位置を (2+1,2)=(3,2)(2+1, 2)=(3, 2) に更新する．
  • 3=3,2=23 = 3, 2 = 2 なので，手続きを終了する．

手続きを終えた後のカウンタの値は 11 です．

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。