Connection Status:
Competition Arena > BalancingAct

BalancingAct

Member SRM 482 · 2010-03-12 · by pieguy

Member SRM 482 · 2010-03-12 · by pieguy · Dynamic Programming, Search
Class Name: BalancingAct
Return Type: String[]
Method Name: recover
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Dave has a balance with which to weigh objects, and a number of reference weights of known value. All weights are integers between 1 and 100000000 (10^8), inclusive. The balance has 2 pans, each of which can hold any number of objects. The balance will indicate which pan contains more total weight, or that the pans contain equal amounts of weight.

Dave has a problem. His arch nemesis, Earl, has removed the labels from some of the weights, in an attempt to prevent Dave from knowing their values. Dave will attempt to recover the values of the unlabeled weights using the balance and the remaining weights. You are asked to figure out if Dave will succeed.

You will be given a int[] labeled giving the values of all of the weights with their labels intact, and int[] unlabeled, the actual values of the unlabeled weights. Return a String[] with the same number of elements as unlabeled, each "yes" if Dave can determine the value of the corresponding unlabeled weight, or "no" otherwise (quotes for clarity only).

Notes

  • Dave knows that the weights are positive integers not exceeding 100000000 (10^8). See example 2.

Constraints

  • labeled will have between 1 and 20 elements, inclusive.
  • unlabeled will have between 1 and 4 elements, inclusive.
  • All elements of labeled will be between 1 and 100000000 (10^8), inclusive.
  • All elements of unlabeled will be between 1 and 100000000 (10^8), inclusive.
Examples
0)
{9,13,15,16}
{19}
Returns: {"yes" }

Dave places the 9 weight and the unlabeled weight in one pan, and the 13 and 15 weights in the other.

1)
{20}
{10,10}
Returns: {"yes", "yes" }

Dave may make multiple weighings.

2)
{33333332,33333334}
{33333333,73,100000000}
Returns: {"yes", "no", "yes" }

Here, Dave uses the fact that all weights are integers between 1 and 100000000.

3)
{12}
{1,1,2,2}
Returns: {"yes", "yes", "yes", "yes" }
4)
{31415926,5358979,32384626,43383279,50288419,
71693993,75105820,9749445,92307816,40628620,
89986280,34825342,11706798,21480865,13282306}
{64709384,46095505,82231725,35940812}
Returns: {"no", "no", "no", "no" }

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

Coding Area

Language: C++17 · define a public class BalancingAct with a public method vector<string> recover(vector<int> labeled, vector<int> unlabeled) · 86 test cases · 2 s / 256 MB per case

Submitting as anonymous