問題一覧 > 通常問題

No.2716 Falcon Method

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 96
作問者 : ecottea / テスター : 👑 p-adic 👑 hamamu
お気に入りにしたユーザー ProblemId : 10596 / 自分の提出
問題文最終更新日: 2024-02-08 21:48:13
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 426 (順位表) の他の問題:

Problem Statement

You are given a string $S = S_0 S_1 \cdots S_{N-1}$ of length $N$ consisting only of D and R (note that the indices start from $0$).

Define the procedure $F(h, w, p)$, which moves on a two-dimensional grid, as follows:

  1. Initialize the position to $(0, 0)$ and the counter value to $p$.
  2. When the current position is $(x, y)$ and the counter value is $i$:
    • If $x = h$ and $y = w$, terminate the procedure.
    • Otherwise, if $x = h$, update the position to $(x, y + 1)$ and return to 2.
    • Otherwise, if $y = w$, update the position to $(x + 1, y)$ and return to 2.
    • Otherwise, where $\bmod$ denotes the binary operator for the remainder:
      • If $S_i=$ D, update the position to $(x + 1, y)$ and the counter to $(i + 1) \bmod N$, and return to 2.
      • If $S_i=$ R, update the position to $(x, y + 1)$ and the counter to $(i + 1) \bmod N$, and return to 2.

You are given $Q$ queries. The $i$-th query is represented by a tuple of integers $(H_i, W_i, P_i)$. Find the counter value after the procedure $F(H_i, W_i, P_i)$ has finished.

Constraints

  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq Q \leq 10^5$
  • $1 \leq H_i, W_i \leq 10^9$
  • $0 \leq P_i < N$
  • $S$ is a string of length $N$ consisting only of D and R
  • All numerical values in the input are integers

Input

The input is given from Standard Input in the following format.

$N \ Q$
$S$
$H_1 \ W_1 \ P_1$
$\vdots$
$H_Q \ W_Q \ P_Q$

Output

Output $Q$ lines. On the $i$-th line, output the counter value after the procedure $F(H_i, W_i, P_i)$ has finished.
Print a newline at the end.

Sample

Sample 1
Input
4 3
RDDR
3 2 1
1 7 0
4 1 3
Output
1
2
0

The $1$-st query is $(3, 2, 1)$, and the procedure $F(3, 2, 1)$ proceeds as follows:

  • Initialize the position to $(0, 0)$ and the counter value to $1$.
  • Since $0 < 3, 0 < 2$ and $S_1=$ D, update the position to $(0+1, 0)=(1, 0)$ and the counter value to $(1+1) \bmod 4 = 2$.
  • Since $1 < 3, 0 < 2$ and $S_2=$ D, update the position to $(1+1, 0)=(2, 0)$ and the counter value to $(2+1) \bmod 4 = 3$.
  • Since $2 < 3, 0 < 2$ and $S_3=$ R, update the position to $(2, 0+1)=(2, 1)$ and the counter value to $(3+1) \bmod 4 = 0$.
  • Since $2 < 3, 1 < 2$ and $S_0=$ R, update the position to $(2, 1+1)=(2, 2)$ and the counter value to $(0+1) \bmod 4 = 1$.
  • Since $2 < 3, 2 = 2$, update the position to $(2+1, 2)=(3, 2)$.
  • Since $3 = 3, 2 = 2$, terminate the procedure.

The counter value after the procedure has finished is $1$.

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