ReverseMancala
SRM 710 · 2017-02-20 · by lg5293
Problem Statement
Mancala is a family of games that are played using tokens (such as seeds or pebbles) that are placed into holes or pits in the ground. In this problem we will call the tokens "stones" and the holes "slots".
You are playing a variant of mancala with n slots around a circle. The slots are labeled from 0 to n-1 in clockwise order. Initially, each slot may contain some stones: for each i, slot i contains start[i] stones.
The game is played in turns. In each turn you do either a type-A move or a type-B move. These look as follows:
- Type A: You choose a non-empty slot and you take all stones from that slot into your hand. Then, while you have some stones in your hand, you repeat the following process: you move one slot clockwise and you drop one stone into that slot. (You might go around the circle several times while doing so, and you might place some of the stones back into the slot you chose at the beginning.)
- Type B: You choose a non-empty slot. Then, while the current slot is non-empty, you repeat the following process: take one stone from the current slot into your hand and then move one slot counter-clockwise. Finally, once you reach an empty slot, deposit all stones from your hand into that slot.
See Examples 0 and 1 for an annotated example of a move of each type.
You are given two
Find and return any sequence of at most 2500 moves that reaches the desired state. For the constraints used in this problem it is guaranteed that such a sequence of moves exists. Note that you do not need to minimize the number of moves, any valid sequence will be accepted.
In order to return a sequence that consists of x moves, return a
- If you chose a type-A move and selected the slot y, the return value should contain the number y.
- If you chose a type-B move and selected the slot y, the return value should contain the number y+n.
Constraints
- start will contain between 2 and 10 elements, inclusive.
- start,target will have the same number of elements.
- Each element of start,target will be between 0 and 10, inclusive.
- The sum of elements in start is positive.
- The sum of elements in start will be the same as the sum of elements in target.
{6, 3, 4, 0}
{1, 5, 6, 1}
Returns: {0 }
This is an example of a type-A move. We can reach the desired distribution of stones by selecting slot 0, i.e., the slot that contains 6 stones. We will then place those 6 stones into slots 1, 2, 3, 0, 1, and 2.
{1, 5, 6, 1}
{6, 3, 4, 0}
Returns: {6 }
This is an example of a type-B move. We can reach the desired distribution of stones by selecting slot 2, i.e., the slot that contains 6 stones. We will then pick up a stone from the slots 2, 1, 0, 3, 2, and 1. Finally, we will reach an empty slot 0 and we will deposit all 6 stones from our hand into this slot. Note that as this is a type-B move, the return value is not 2 but 2+4 = 6.
{10, 0, 1, 2, 3}
{10, 0, 0, 2, 4}
Returns: {2, 4, 8 }
Note that during the game a slot may contain more than 10 stones. The return value shown above corresponds to the following sequence of moves: A type-A move selecting slot 2. This brings the game into the state (10,0,0,3,3). A type-A move selecting slot 4. This brings the game into the state (11,1,1,3,0). A type-B move selecting slot 8-5 = 3. This brings the game into the desired state (10,0,0,2,4).
{2, 0, 1, 7}
{0, 2, 1, 7}
Returns: {2, 0, 1, 7 }
{3, 2, 4, 5}
{0, 1, 6, 7}
Returns: {7, 1, 0, 7, 1, 0 }
Submissions are judged against all 95 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ReverseMancala with a public method vector<int> findMoves(vector<int> start, vector<int> target) · 95 test cases · 2 s / 256 MB per case