SpecialWeights | Topcoder Archive

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.

Definition

Class:: SpecialWeights
Method:: solve
Parameters:: int, long[], long
Returns:: long
Method signature:: long solve(int N, long[] W, long K)
(be sure your method is public)

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.

Examples

```
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.

{100000000000, 300000000000, 700000000000, 1300000000000, 3000000000000}

Returns: 1400000000000

Watch out for integer overflow.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.