WeighingScale
SRM 361 · 2007-08-01 · by slex
Problem Statement
Little George has found an old-fashioned balance scale and a set of weights in the attic. The scale has two weighing pans and it allows you to check if the content of the left pan is heavier, lighter, or the same weight as the content of the right pan. The box where the weights were kept says that each of them weigh 10, 20, or 30 grams, but the faded paint makes it impossible to tell which is which.
George started playing with the scale by comparing one weight against another, and noting down all his results. After a while he got bored with that, and came up with a new experiment. He put the A-th and B-th weights on the left pan and tried to guess what would happen when he put another two weights on the right pan.
You are given a
- '+' - the i-th weight is heavier than the j-th weight.
- '-' - the i-th weight is lighter than the j-th weight.
- '=' - both weights have the same weight.
- '?' - the two weights weren't compared.
Notes
- Since the weights with indices A and B are already on the left pan you should only consider pairs that contain neither A nor B for the right pan.
Constraints
- measures will contain between 4 and 50 elements, inclusive.
- Each element of measures will contain exactly N characters, where N is the number of elements in measures.
- Each element of measures will contain only '+','-', '=', or '?'.
- The i-th character of the i-th element of measures will be '?'
- If the j-th character of the i-th element of measures is '+' than the i-th character of the j-th element will be '-' and vice versa.
- If the j-th character of the i-th element of measures is '=' or '?' than the i-th character of the j-th element will be the same.
- There will exist at least one way to assign values to the weights that will match the results in measures.
- A will be between 0 and N-1, inclusive, where N is the number of elements in measures.
- B will be between 0 and N-1, inclusive, where N is the number of elements in measures.
- A will be different than B.
{"?+????","-?+???","?-????","????+?", "???-?+","????-?"}
1
4
Returns: {1, 4, 1 }
We have the following weight relations: w0 > w1 > w2 w3 > w4 > w5 It can only be true if the values are (30,20,10,30,20,10). The left pan contains weights 1 and 4 with total weight 20+20=40. There is one pair (0,3) heavier than that, one pair (2,5) lighter than that and the remaining four pairs have the same weight.
{"?+?????","-?+????","?-?????","????+??", "???-?+?","????-??", "???????"}
0
3
Returns: {10, 0, 0 }
The first six weights are the same as in example 0 (30,20,10,30,20,10). We know nothing about the 7th weight, but still, putting the two 30 gram weights on the left pan assures that it will be heavier than any other pair.
{"?+?????","-?+????","?-?????","????+??", "???-?+?","????-??", "???????"}
1
4
Returns: {1, 4, 1 }
With the same measures as in the previous example, now weights 1 and 4 lie on the left pan, for a total weight of 40. We can predict what will happen only if the pair on the right pan doesn't contain the 7th weight; otherwise it's impossible to tell.
{"??+?", "???+", "-???", "?-??"}
0
1
Returns: {1, 0, 0 }
We know that w0 > w2 and w1 > w3 thus w0+w1 must be heavier than w2+w3.
{"??+??", "???+?", "-???=", "?-???", "??=??"}
0
1
Returns: {3, 0, 0 }
Submissions are judged against all 82 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WeighingScale with a public method vector<int> count(vector<string> measures, int A, int B) · 82 test cases · 2 s / 256 MB per case