StepHopJumpConstruct
SRM 814 · 2021-09-28 · by misof
Problem Statement
You are designing a new video game.
In this video game, each level is a rectangular room divided into blocks. Some blocks are solid terrain blocks (denoted '-') and others contain spiky traps (denoted '*'). If the player steps onto a trap, they die.
The player starts the game in the northwest corner of the room. Their goal is to reach the opposite (southeast) corner of the room. Both the starting block and the goal block must be solid terrain blocks ('-').
The player can move in three ways: making a step, a hop, or a jump. Each movement must go either to the east, or to the south. A step takes the player to the next block in that direction, a hop skips over one block and lands on the second one, and a jump skips over two blocks and lands on the third one. (You can hop or jump over blocks with spikes without dying. You cannot make a move that would leave the room.)
For example, consider the following level (north is on the top, west is on the left - i.e., we start in the top left corner and we go to the bottom right):
-**-**-
*******
-*-*-*-
There are two ways in which a player can traverse this level: either they make two jumps east and then a hop south, or they start by a hop south and continue by making three hops east. (In all other ways of moving, the player would either move outside the level, or they would step onto spikes and die.)
You are given an
Design a level that can be traversed in exactly W distinct ways.
The level must be rectangular, it must have between 2 and 50 rows (inclusive) and between 2 and 50 columns (inclusive). Also, remember that the start and end of a level must be solid blocks.
Return a
Notes
- For the given constraints a solution always exists.
Constraints
- W will be between 0 and 10^9, inclusive.
4
Returns: {"----", "***-" }
The returned level: ---- ***- The level can be traversed in four different ways. In each of them we first move only to the right and then we take a step down. While moving to the right, we can do either three steps, or a hop + a step, or a step + a hop, or a jump. (Note that we cannot just return {"----"}, as the level must have at least two rows.)
2
Returns: {"-**-**-", "*******", "-*-*-*-" }
The returned level is the one described in the statement. Many other solutions exist.
7
Returns: {"-**", "-**", "-**", "-**", "-*-" }
The returned level: -** -** -** -** -*- There are seven ways in which we can move southwards from the start. Once we reach the southwest (i.e., bottom left) corner, we must finish the solution by making a hop to the right.
106
Returns: {"----", "----", "----", "----" }
The returned solution is a 4x4 board with no traps. Two of the 106 possible ways of traversing this level are "a jump east and then a jump south" and "a jump south and then a jump east". Another solution is a sequence of six steps, going alternately east and south. Yet another solution is a step south, a jump east, and two more steps south.
0
Returns: {"-*", "*-" }
Remember that a valid level must have a solid block as its start and end, even if we want zero solutions.
Submissions are judged against all 157 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class StepHopJumpConstruct with a public method vector<string> construct(int W) · 157 test cases · 2 s / 256 MB per case