codeforces-scrape

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

2150A.md (3205B)


      1 Source: https://codeforces.com/problemset/problem/2150/A
      2 
      3 A. Incremental Path
      4 
      5 time limit per test
      6 
      7 1 second
      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 [Rymdkraft - Rymdsylt](https://soundcloud.com/rymdkraft/rymdsylt)
     22 
     23 ⠀
     24 
     25 Hacks are disabled in this problem.
     26 
     27 There is a strip containing $10^9$ cells, numbered from $1$ to $10^9$. Each cell is either black or white. Initially, $m$ distinct cells $a_1, a_2, \ldots, a_m$ are black, and the others are white.
     28 
     29 If a person is on some cell $x$, he might be given two types of commands:
     30 
     31 * $\texttt{A}$: jump to the next cell, i.e. cell $x + 1$;
     32 * $\texttt{B}$: jump to the next white cell, i.e. the minimum $y \gt x$ such that cell $y$ is white.
     33 
     34 There is a string $s$ of length $n$, consisting of $n$ commands. For each $i$ from $1$ to $n$ in order, a person
     35 
     36 * starts from cell $1$;
     37 * executes the first $i$ commands in the string;
     38 * colors the last visited cell black (if it was already black, it remains black).
     39 
     40 You wonder which cells are black at the end of the process. Print them in increasing order.
     41 
     42 Input
     43 
     44 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     45 
     46 The first line of each test case contains two integers $n$ and $m$ ($1 \leq n \leq 10^5$, $1 \leq m \leq 10^5$) — the number of commands and the number of black cells at the beginning.
     47 
     48 The second line of each test case contains a string $s$ of length $n$, consisting of characters $\texttt{A}$ and $\texttt{B}$, representing the commands.
     49 
     50 The third line of each test case contains $m$ integers $a_1, a_2, \ldots, a_m$ ($1 \leq a_1 \lt a_2 \lt \ldots \lt a_m \leq 10^9$) — the initial black cells.
     51 
     52 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$, and the sum of $m$ over all test cases does not exceed $10^5$.
     53 
     54 Output
     55 
     56 For each test case, print two lines:
     57 
     58 * in the first line, print a single integer $k$: the number of black cells at the end;
     59 * in the second line, print the labels of the black cells, in increasing order.
     60 
     61 Example
     62 
     63 Input
     64 
     65 ```
     66 5
     67 
     68 3 2
     69 
     70 BAB
     71 
     72 2 5
     73 
     74 3 4
     75 
     76 ABA
     77 
     78 1 4 9 10
     79 
     80 5 2
     81 
     82 ABABB
     83 
     84 1 7
     85 
     86 3 1
     87 
     88 BBA
     89 
     90 6
     91 
     92 1 4
     93 
     94 A
     95 
     96 1 3 4 1000000000
     97 ```
     98 
     99 Output
    100 
    101 ```
    102 4
    103 
    104 2 3 5 6
    105 
    106 7
    107 
    108 1 2 3 4 6 9 10
    109 
    110 7
    111 
    112 1 2 3 5 6 7 9
    113 
    114 3
    115 
    116 2 4 6
    117 
    118 5
    119 
    120 1 2 3 4 1000000000
    121 ```
    122 
    123 Note
    124 
    125 In the first test case, initially the only black cells are $2$ and $5$.
    126 
    127 Person $1$:
    128 
    129 * starts from cell $1$;
    130 * executes command $\texttt{B}$, going to the next white cell ($3$);
    131 * colors cell $3$ black.
    132 
    133 Person $2$:
    134 
    135 * starts from cell $1$;
    136 * executes command $\texttt{B}$, going to the next white cell ($4$);
    137 * executes command $\texttt{A}$, going to the next cell ($5$);
    138 * colors cell $5$ black (it was already black, so it remains black).
    139 
    140 Person $3$:
    141 
    142 * starts from cell $1$;
    143 * executes command $\texttt{B}$, going to the next white cell ($4$);
    144 * executes command $\texttt{A}$, going to the next cell ($5$);
    145 * executes command $\texttt{B}$, going to the next white cell ($6$);
    146 * colors cell $6$ black.
    147 
    148 At the end, the black cells are $\{2, 3, 5, 6\}$.
    149 
    150 In the second test case, the three people end up in cells $2$, $3$, and $6$, respectively.