Black-Red Square
Time limit2sMemory limit256 MB
Construct a rolling-square walk on a grid that paints exactly r cells red and b cells black, where the color of each visited cell alternates.
- Level
Medium5 of 10
- Topics
- Implementation, Simulation, Greedy, Math
- Solved
- No attempts yet
Statement
On an infinite grid board there is an unusual chess piece: the black-red square. This piece is a square that occupies exactly one cell of the board, with one face painted black and the other painted red. Unlike ordinary chess pieces, the black-red square leaves traces on the board. Each cell it has visited is painted black or red, depending on which face of the square pointed downward while it was on that cell.
In one move the square can roll to an adjacent cell. As it does, it flips over: if it was lying black side up, it ends up black side down, and vice versa. The cell it rolls into is painted with the color of the square's bottom face. Initially the square lies black side down, so the starting cell of its path is painted black.
Initially every cell of the board is painted white. Find some path of the square after which the board has exactly red cells and exactly black cells. At least one such path is guaranteed to exist.
Input
The single line contains two integers and (; ).
Output
On the first line print the number of moves the square makes. must not exceed 100,000.
On the second line print the square's path: a string of length consisting of the letters N, S, W, E. These letters denote moves up, down, left, and right, respectively.
If there are several answers, print any of them. At least one answer is guaranteed to exist.