BalanceScale
SRM 358 · 2007-07-17 · by icanadi
SRM 358 · 2007-07-17 · by icanadi · Brute Force, Math
Problem Statement
Problem Statement
You are given a int[] weight, a set of weight values. You must choose the minimum number of weight values from the set such that every element in weight is measurable on a balance scale with the chosen weight values. Weight X is measurable with a set Y of weight values if and only if you can do the following. You place one weight with value X on either the left or right side of the scale. You then place some combination of weights on the scale with values from the set Y so that the left and right sides have the same total value. You may use each value in Y zero or more times to achieve this.
For example, consider the set of weight values { 21, 9, 6 }. You can choose the set { 9, 6 }, and every element in the original set will be measurable with this set. With weight 21, you can do the following. Place the one weight of 21 on the left side of the scale. Then place one weight of value 9 on the left side, and 5 weights of value 6 on the right side, and the scale will be balanced. With weights 9 and 6, you can simply place the weight on one side and a weight of equal value on the opposite side to balance the scale.
Return the minimum number of chosen weight values.
For example, consider the set of weight values { 21, 9, 6 }. You can choose the set { 9, 6 }, and every element in the original set will be measurable with this set. With weight 21, you can do the following. Place the one weight of 21 on the left side of the scale. Then place one weight of value 9 on the left side, and 5 weights of value 6 on the right side, and the scale will be balanced. With weights 9 and 6, you can simply place the weight on one side and a weight of equal value on the opposite side to balance the scale.
Return the minimum number of chosen weight values.
Constraints
- weight will contain between 1 and 50 elements, inclusive.
- All elements of weight will be distinct.
- Each element of weight will be between 1 and 10,000,000, inclusive.
Examples
0)
{ 5, 4, 1, 8 }
Returns: 1
With weight value 1 we can measure all the other elements.
1)
{ 2, 3, 8, 9 }
Returns: 2
We choose weight values 2 and 3. Measure 8 by placing the weight of 8 on the left side, and 4 weights of value 2 on the right side. Measure 9 by placing the weight of 9 on the left side, and 3 weights of value 3 on the right side.
2)
{ 2466, 274, 2603, 3151 }
Returns: 2
3)
{ 60, 105, 490, 42 }
Returns: 4
We can choose all weight values from the set.
4)
{ 15, 25, 9 }
Returns: 2
Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BalanceScale with a public method int takeWeights(vector<int> weight) · 77 test cases · 2 s / 256 MB per case