CoinConstruction | Topcoder Archive

Problem Statement

This task is about a bag of coins. Each coin in the bag has a positive integer value. The values are not necessarily distinct. A positive integer X is called good if there is a nonempty subset of coins such that their total value is exactly X. We will use S to denote the set of all good integers.

Here are some examples:

If the bag contains coins with values 3, 4, 7, the set S will be {3, 4, 7, 10, 11, 14}.
If the bag contains coins with values 2, 2, 10, the set S will be {2, 4, 10, 12, 14}.

You are given an int k. Construct a bag of coins with the following properties:

The set S of good integers has exactly k elements.
The bag must contain between 1 and 20 coins, inclusive.
The value of each coin must be between 1 and 10^9, inclusive.

Note that your bag may contain multiple coins with the same value. We guarantee that for the constraints used in this task there is always a solution. If there are multiple solutions, you may choose any one of them.

Return a int[] containing the values of the coins in your bag.

Definition

Class:: CoinConstruction
Method:: construct
Parameters:: int
Returns:: int[]
Method signature:: int[] construct(int k)
(be sure your method is public)

Constraints

k will be between 1 and 1,000,000, inclusive.

Examples

```
6
```
```
Returns: {3, 4, 7 }
```
This is the case mentioned in the statement: S = {3, 4, 7, 10, 11, 14}.
```
26
```
```
Returns: {1, 1, 10, 10, 100, 100 }
```
This time S contains all values of the form (a * 100 + b * 10 + c) where a, b, c are in {0, 1, 2}, except for a = b = c = 0.
```
7
```
```
Returns: {1, 1, 1, 1, 1, 1, 1 }
```
```
1
```
```
Returns: {999999999 }
```

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.