VisitN

TCO19 SRM 750 · 2019-01-09 · by misof

TCO19 SRM 750 · 2019-01-09 · by misof · Greedy, Search, Simple Math

Show categories

Class Name: VisitN

Return Type: String

Method Name: visit

Arg Types: (int, int, int)

Problem Statement

You are on a 30x30 chessboard. The rows of the chessboard are numbered 0 through 29 from the north to the south. The columns of the chessboard are numbered 0 through 29 from the west to the east. Your starting cell is (r,c).

Your task is to visit exactly n cells of the chessboard (including the one where you start). You can move in steps. In each step you can move one cell in one of the four cardinal directions: north, south, east, or west. We will denote these movements 'N', 'S', 'E', and 'W'. You may visit the same cell multiple times. You may not leave the chessboard. (E.g., if you are in row 0, you cannot move north.)

Return a String with at most 2000 characters: any sequence of moves that never leaves the chessboard and visits exactly n distinct cells.

Constraints

n will be between 1 and 900, inclusive.
r will be between 0 and 29, inclusive.
c will be between 0 and 29, inclusive.

Examples

1
4
7
Returns: ""

The only way to visit exactly one cell is to make no steps at all.

2
4
7
Returns: "N"

By taking a step north we have visited two cells: the cell (4,7) where we started and the cell (3,7) we just reached.

2
0
17
Returns: "W"

This time we are on the north end of the chessboard, so we cannot take a step north. Other valid solutions include "E", "S", and "SNSNSNS".

4
1
1
Returns: "NWEE"

Note that this path visits the cell (0,1) twice, so the number of distinct cells it visits is 4, not 5.

10
5
13
Returns: "NWSSEENNSSWS"

Submissions are judged against all 162 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class VisitN with a public method string visit(int n, int r, int c) · 162 test cases · 2 s / 256 MB per case