SpecialWeights
SRM 845 · 2023-03-02 · by misof
Problem Statement
Mary has a collection of N stones. The stones are numbered from 0 to N-1.
For each i, the weight W[i] of stone number i is a positive integer.
For each i, stone number i weighs more than all stones with smaller numbers together.
Mary sometimes uses her collection of stones when weighing an object on balance scales: she places the object onto one plate, some stones on the other plate, and if the two plates are in a balance, she knows that the object weighs the same as the collection of stones.
Of course, not all objects can be weighed using the above method: sometimes there is no combination of stones that weighs the same as the object.
A weight x >= 0 is called admissible if we can balance an object of weight x with some (possibly empty) collection of Mary's stones.
For example, if Mary's stones have weights 4 and 7, the admissible weights are 0, 4, 7, and 11.
Consider the strictly increasing sequence of all distinct admissible weights. Return the element at (1-based) index K in this sequence, or -1 if no such element exists.
Notes
- As 0 is the weight of an empty collection of stones, the weight 0 is always the smallest admissible weight.
- The answer always fits into a signed 64-bit integer variable. (Note that the largest possible answer is the sum of all weights given in the input.)
Constraints
- N will be between 1 and 50, inclusive.
- W will have exactly N elements.
- All elements of W will be positive.
- For each i, W[i] will be greater than the sum of all W[j] where j < i.
- The sum of W will not exceed 10^18.
- K will be between 1 and 10^18, inclusive.
2
{4, 7}
1
Returns: 0
As we already mentioned above, for these stones the sequence of admissible weights is {0, 4, 7, 11}. As K = 1, we want the first (i.e., smallest) one.
2
{4, 7}
4
Returns: 11
This time we return the largest admissible weight: 11.
2
{4, 7}
5
Returns: -1
There are only four distinct admissible weights. Thus, there is no admissible weight with index 5 and therefore we have to return -1.
5
{1, 3, 7, 13, 30}
10
Returns: 14
Sorted list of all distinct admissible weights for these stones: 0, 1, 3, 4, 7, 8, 10, 11, 13, 14, 16, 17, 20, 21, 23, 24, 30, 31, 33, 34, 37, 38, 40, 41, 43, 44, 46, 47, 50, 51, 53, 54. On (1-based) position 10 in this list we see the number 14, so that is the correct return value.
38
{1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987, 22876792454961, 68630377364883, 205891132094649, 617673396283947, 1853020188851841, 5559060566555523, 16677181699666569, 50031545098999707, 150094635296999121, 450283905890997363}
1
Returns: 0
5
{100000000000, 300000000000, 700000000000, 1300000000000, 3000000000000}
10
Returns: 1400000000000
Watch out for integer overflow.
Submissions are judged against all 67 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SpecialWeights with a public method long long solve(int N, vector<long long> W, long long K) · 67 test cases · 2 s / 256 MB per case