Connection Status:
Competition Arena > MoveStonesEasy

MoveStonesEasy

SRM 683 · 2016-01-04 · by Arterm

SRM 683 · 2016-01-04 · by Arterm · Simple Search, Iteration
Class Name: MoveStonesEasy
Return Type: int
Method Name: get
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

There are n piles of stones arranged in a line. The piles are numbered 0 through n-1, in order. In other words, for each valid i, piles i and i+1 are adjacent.

You are given two int[]s a and b, each with n elements. For each i, a[i] is the current number of stones in pile i, and b[i] is the desired number of stones for this pile. You want to move some stones to create the desired configuration. In each step you can take any single stone from any pile and move the stone to any adjacent pile. Find and return the smallest number of steps needed to create the desired configuration, or -1 if the desired distribution of stones cannot be reached.

Notes

  • At any moment during the game some piles may be empty. Empty piles still remain in place. For example, if pile 5 is empty, you are not allowed to move a stone from pile 4 directly to pile 6 in a single step. Instead, you must place the stone onto the empty pile 5 first.

Constraints

  • n will be between 1 and 50, inclusive.
  • a will have exactly n elements.
  • b will have exactly n elements.
  • Each element of a and b will be between 0 and 1,000,000 (10^6), inclusive.
Examples
0)
{1, 2}
{2, 1}
Returns: 1

We need to move one stone from pile 1 to pile 0.

1)
{10, 0}
{0, 10}
Returns: 10
2)
{0, 0, 1}
{1, 0, 0}
Returns: 2

Note that in a single step we can only move a stone between adjacent piles. Hence, we need two steps to move a stone from pile 2 to pile 0.

3)
{12, 12}
{12, 12}
Returns: 0

The desired configuration of stones is the same as the current configuration. No steps necessary.

4)
{5}
{6}
Returns: -1

We cannot add or remove stones, we can only move them between piles.

5)
{3,10,0,4,0,0,0,1,0}
{5,5,0,7,0,0,0,0,1}
Returns: 9

Move 2 stones from pile 1 to pile 0. Move 3 stones from pile 1 to pile 2. Move 3 stones from pile 2 to pile 3. Move 1 stone between two last piles. The total number of steps is 2 + 3 + 3 + 1 = 9.

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

Coding Area

Language: C++17 · define a public class MoveStonesEasy with a public method int get(vector<int> a, vector<int> b) · 31 test cases · 2 s / 256 MB per case

Submitting as anonymous