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  114 115 For WWW, the solution is impossible.