PaintTheRoom
SRM 668 · 2015-08-31 · by zxqfl
Problem Statement
The floor is a grid of cells with R rows and C columns. Little Liz occupies a position in this grid. She can move up, down, left, or right. (She cannot move diagonally.) To ensure that each cell gets the appropriate amount of paint, Liz should visit each cell exactly K times. Liz visits a cell whenever she moves into it. Liz also visits a cell if she begins her walk on it. Liz can begin and end on any cell.
If it is possible to paint the room in the required way, return "Paint". Otherwise, return "Cannot paint". (All quotes are for clarity only.)
Constraints
- R will be between 1 and 50, inclusive.
- C will be between 1 and 50, inclusive.
- K will be between 1 and 50, inclusive.
Statement by TopCoder, Inc. — view the original on the archive.
1 1 1 Returns: "Paint"
There is only one cell in this grid. By starting on the cell, Little Liz visits it once.
1 1 2 Returns: "Cannot paint"
This is the same case as Example 0, but now the cell must be visited twice. This is impossible.
1 2 2 Returns: "Paint"
There are two cells, and they are in the same row. One possible solution is to start on the left cell, then move right, then left, then right. This visits each cell twice, as required.
2 2 3 Returns: "Paint"
1 1 1 Returns: "Paint"
Submissions are judged against all 94 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PaintTheRoom with a public method string canPaintEvenly(int R, int C, int K) · 94 test cases · 2 s / 256 MB per case