G. Robot Walk

Codeforces

IDCF10079G

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Bob has built a tiny robot whose movement he can program. He also has a board that consists of n cells lined up in a row, numbered 1 to n from left to right. Each of the cells also has a single letter written on it. Initially Bob places the robot in the cell number x. Then Bob executes a program that moves the robot on the board. One instruction of the program will move the robot either one cell to the left or one cell to the right. The robot also has a photo sensor directed at the board, and whenever Bob changes the location of the robot (including placing it in the initial cell), it recognizes and sends the letter that is written in the cell to Bob's computer. After the robot finishes the program, the computer prints the received text. Given the program of m moves for the robot, print out the text the computer will output. The program consists of characters "_L_" and "_R_", which mean that the robot should move one cell to the left or to the right, respectively. The first line contains two space-separated integers n and x (2 ≤ n < 105, 1 ≤ x ≤ n). The second line contains a string s of length n: the i-th character of s is the letter written in the cell number i. The string s will consist of lowercase latin letters. The third line contains a single integer m — the length of the program (1 ≤ m ≤ 105). The fourth line contains the program consisting of symbols "_L_" and "_R_". It is guaranteed that the program will not cause the robot to leave the board. In a single line output the text printed out by the computer. ## Input The first line contains two space-separated integers n and x (2 ≤ n < 105, 1 ≤ x ≤ n). The second line contains a string s of length n: the i-th character of s is the letter written in the cell number i. The string s will consist of lowercase latin letters. The third line contains a single integer m — the length of the program (1 ≤ m ≤ 105). The fourth line contains the program consisting of symbols "_L_" and "_R_".It is guaranteed that the program will not cause the robot to leave the board. ## Output In a single line output the text printed out by the computer. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of cells. Let $ x \in \{1, \dots, n\} $ be the initial position of the robot. Let $ s \in \Sigma^n $ be a string of length $ n $, where $ \Sigma $ is the set of lowercase Latin letters, and $ s[i] $ is the letter on cell $ i $. Let $ m \in \mathbb{Z} $ be the number of instructions. Let $ p \in \{L, R\}^m $ be the program sequence. **Constraints** 1. $ 2 \leq n < 10^5 $ 2. $ 1 \leq x \leq n $ 3. $ 1 \leq m \leq 10^5 $ 4. The robot never moves outside $ [1, n] $. **Objective** Simulate the robot's movement starting at position $ x $, and output the sequence of letters $ s[\text{position}] $ collected at each step (including the initial placement). Let $ \text{pos}_0 = x $, and for $ j \in \{1, \dots, m\} $: $$ \text{pos}_j = \begin{cases} \text{pos}_{j-1} - 1 & \text{if } p[j] = L \\ \text{pos}_{j-1} + 1 & \text{if } p[j] = R \end{cases} $$ Output the string: $$ s[\text{pos}_0] \cdot s[\text{pos}_1] \cdot \dots \cdot s[\text{pos}_m] $$ where $ \cdot $ denotes concatenation, and positions are 1-indexed.

API Response (JSON)

{
  "problem": {
    "name": "G. Robot Walk",
    "description": {
      "content": "Bob has built a tiny robot whose movement he can program. He also has a board that consists of n cells lined up in a row, numbered 1 to n from left to right. Each of the cells also has a single letter",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10079G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bob has built a tiny robot whose movement he can program. He also has a board that consists of n cells lined up in a row, numbered 1 to n from left to right. Each of the cells also has a single letter...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of cells.  \nLet $ x \\in \\{1, \\dots, n\\} $ be the initial position of the robot.  \nLet $ s \\in \\Sigma^n $ be a string of length $ n $, where $ \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments