codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1932C.md (2601B)


      1 Source: https://codeforces.com/problemset/problem/1932/C
      2 
      3 C. LR-remainders
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an array $a$ of length $n$, a positive integer $m$, and a string of commands of length $n$. Each command is either the character 'L' or the character 'R'.
     22 
     23 Process all $n$ commands in the order they are written in the string $s$. Processing a command is done as follows:
     24 
     25 * First, output the remainder of the product of all elements of the array $a$ when divided by $m$.
     26 * Then, if the command is 'L', remove the leftmost element from the array $a$, if the command is 'R', remove the rightmost element from the array $a$.
     27 
     28 Note that after each move, the length of the array $a$ decreases by $1$, and after processing all commands, it will be empty.
     29 
     30 Write a program that will process all commands in the order they are written in the string $s$ (from left to right).
     31 
     32 Input
     33 
     34 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then descriptions of $t$ test cases follow.
     35 
     36 Each test case of the input is given by three lines.
     37 
     38 The first line contains two integers $n$ and $m$ ($1 \le n \le 2\cdot10^5, 1 \le m \le 10^4$) — the initial length of the array $a$ and the value to take the remainder by.
     39 
     40 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^4$) — the elements of the array $a$.
     41 
     42 The third line contains a string $s$ consisting of $n$ characters 'L' and 'R'.
     43 
     44 It is guaranteed that the sum of the values of $n$ for all test cases in a test does not exceed $2\cdot10^5$.
     45 
     46 Output
     47 
     48 For each test case, output $n$ integers $b_1, b_2, \dots, b_n$, where $b_i$ is the remainder when dividing the product of all elements of the current state of the array $a$ by $m$ at the beginning of the execution of the $i$-th command.
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 4
     56 
     57 4 6
     58 
     59 3 1 4 2
     60 
     61 LRRL
     62 
     63 5 1
     64 
     65 1 1 1 1 1
     66 
     67 LLLLL
     68 
     69 6 8
     70 
     71 1 2 3 4 5 6
     72 
     73 RLLLRR
     74 
     75 1 10000
     76 
     77 10000
     78 
     79 R
     80 ```
     81 
     82 Output
     83 
     84 ```
     85 0 2 4 1 
     86 0 0 0 0 0 
     87 0 0 0 4 4 4 
     88 0
     89 ```
     90 
     91 Note
     92 
     93 In the first test case of the example:
     94 
     95 * $3 \cdot 1 \cdot 4 \cdot 2 \bmod 6 = 24 \bmod 6 = 0$;
     96 * $s_1 = \text{L}$, so we remove the first element and get the array $[1, 4, 2]$;
     97 * $1 \cdot 4 \cdot 2 \bmod 6 = 8 \bmod 6 = 2$;
     98 * $s_2 = \text{R}$, so we remove the last element and get the array $[1, 4]$;
     99 * $1 \cdot 4 \bmod 6 = 4 \bmod 6 = 4$;
    100 * $s_3 = \text{R}$, so we remove the last element and get the array $[1]$;
    101 * $1 \bmod 6 = 1$;
    102 * $s_4 = \text{L}$, so we remove the first element and get an empty array.