CubeRoll
SRM 507 · 2010-11-01 · by ir5
Problem Statement
NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.
Fox Ciel is competing against Fox Jiro in a game called cube roll.
Cube roll is played on a horizontal row of cells. Cells are numbered consecutively, increasing from left to right. The row is infinitely long, so all integers, including negative ones, are valid cell numbers. Certain cells contain holes, and they are given in the
Initially, a cube is placed at cell initPos. The objective of the game is to move the cube to cell goalPos using the least possible number of turns. On each turn, the player will choose a direction (left or right) and roll the cube in that direction by x number of cells, where x is a perfect square (1, 4, 9, 16, ...). If at any time during the roll, the cube lands on a cell containing a hole, the cube will fall into the hole. Once the cube falls into a hole, it can never be moved again.
Return the minimum number of turns required to move the cube to cell goalPos. If it is impossible, return -1 instead.
Constraints
- initPos and goalPos will each be between 1 and 100,000, inclusive.
- holePos will contain between 1 and 50 elements, inclusive.
- Each element of holePos be between 1 and 100,000, inclusive.
- initPos and goalPos and all elements of holePos will be distinct.
5
1
{3}
Returns: -1
There is a hole between initPos and goalPos, so the cube cannot be moved from initPos to goalPos.
36
72
{300, 100, 200, 400}
Returns: 1
The distance between initPos and goalPos is a perfect square, and there are no holes between them, so the cube can be moved in a single turn.
10
21
{38,45}
Returns: 2
One of the optimal solutions is to move the cube to 10 -> -15 -> 21. (Note that the coordinate of the cube can be a negative integer.)
98765
4963
{10,20,40,30}
Returns: 2
68332
825
{99726,371,67,89210}
Returns: 2
Submissions are judged against all 150 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CubeRoll with a public method int getMinimumSteps(int initPos, int goalPos, vector<int> holePos) · 150 test cases · 2 s / 256 MB per case