codeforces-scrape

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

1974D.md (2500B)


      1 Source: https://codeforces.com/problemset/problem/1974/D
      2 
      3 D. Ingenuity-2
      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 Let's imagine the surface of Mars as an infinite coordinate plane. Initially, the rover Perseverance-2 and the helicopter Ingenuity-2 are located at the point with coordinates $(0, 0)$. A set of instructions $s$ consisting of $n$ instructions of the following types was specially developed for them:
     22 
     23 * N: move one meter north (from point $(x, y)$ to $(x, y + 1)$);
     24 * S: move one meter south (from point $(x, y)$ to $(x, y - 1)$);
     25 * E: move one meter east (from point $(x, y)$ to $(x + 1, y)$);
     26 * W: move one meter west (from point $(x, y)$ to $(x - 1, y)$).
     27 
     28 Each instruction must be executed either by the rover or by the helicopter. Moreover, each device must execute at least one instruction. Your task is to distribute the instructions in such a way that after executing all $n$ instructions, the helicopter and the rover end up at the same point, or determine that this is impossible.
     29 
     30 Input
     31 
     32 The first line of input contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     33 
     34 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of instructions.
     35 
     36 The second line of each test case contains a string $s$ of length $n$ consisting of the characters 'N', 'S', 'E', 'W' — the sequence of instructions.
     37 
     38 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10 ^ 5$.
     39 
     40 Output
     41 
     42 For each test case, if the required distribution of instructions exists, output a string $p$ of length $n$ consisting of the characters 'R', 'H'. If the $i$-th operation should be executed by the rover, then $p_i=\text{R}$, if the $i$-th operation should be executed by the helicopter, then $p_i=\text{H}$. If there are multiple solutions, output any of them.
     43 
     44 Otherwise, output NO.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 10
     52 
     53 6
     54 
     55 NENSNE
     56 
     57 3
     58 
     59 WWW
     60 
     61 6
     62 
     63 NESSWS
     64 
     65 2
     66 
     67 SN
     68 
     69 2
     70 
     71 WE
     72 
     73 4
     74 
     75 SSNN
     76 
     77 4
     78 
     79 WESN
     80 
     81 2
     82 
     83 SS
     84 
     85 4
     86 
     87 EWNN
     88 
     89 4
     90 
     91 WEWE
     92 ```
     93 
     94 Output
     95 
     96 ```
     97 RRHRRH
     98 NO
     99 HRRHRH
    100 NO
    101 NO
    102 RHRH
    103 RRHH
    104 RH
    105 RRRH
    106 RRHH
    107 ```
    108 
    109 Note
    110 
    111 Let's consider the first example: the string $S = \texttt{NENSNE}$. One of the possible solutions, shown in the figure below, is $p = \texttt{RRHRRH}$, using which both the rover and the helicopter will end up one meter north and one meter east.
    112 
    113  ![](https://espresso.codeforces.com/c575ad2784955759002dfe4a0a9a414a9da0b94a.png) 
    114 
    115 For WWW, the solution is impossible.