Halving
SRM 728 · 2018-01-24 · by tourist
Problem Statement
You have a collection of sticks. The length of each stick is a positive integer.
You want to have a collection of sticks in which all the sticks have the same length. You may alter your current collection by performing zero or more steps. Each step must look as follows:
- You choose one of your sticks. The chosen stick must have length at least 2.
- Let L be the length of the chosen stick.
- If L is even, cut the stick into two sticks of length L/2 each. Otherwise, cut it into sticks of lengths (L-1)/2 and (L+1)/2.
- Keep one of the two new sticks and throw away the other one.
It can be proved that any collection of sticks can be turned into a collection of sticks that all have the same length.
You are given the current lengths of your sticks in the
Constraints
- a will contain between 2 and 50 elements, inclusive.
- Each element of a will be between 1 and 109, inclusive.
{11, 4}
Returns: 3
One optimal solution is: Pick the stick of length 11, cut it into sticks of lengths 5 and 6 and keep the part of length 5. Pick the stick of length 4, cut it into two sticks of length 2 and keep the part of length 2. Pick the stick of length 5, cut it into sticks of lengths 2 and 3 and keep the part of length 2. In the end, you'll have two sticks of length 2.
{1000000000, 1000000000, 1000000000, 1000000000}
Returns: 0
All your sticks have the same length, no steps are needed.
{1, 2, 3, 4, 5, 6, 7}
Returns: 10
{13, 13, 7, 11, 13, 11}
Returns: 11
{1, 1}
Returns: 0
Submissions are judged against all 51 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Halving with a public method int minSteps(vector<int> a) · 51 test cases · 2 s / 256 MB per case