CF1974D Ingenuity-2

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: - N: move one meter north (from point $ (x, y) $ to $ (x, y + 1) $ ); - S: move one meter south (from point $ (x, y) $ to $ (x, y - 1) $ ); - E: move one meter east (from point $ (x, y) $ to $ (x + 1, y) $ ); - W: move one meter west (from point $ (x, y) $ to $ (x - 1, y) $ ). 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.

N/A

N/A

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