CoinConstruction

TCO17 Round 1B · 2017-03-31 · by cgy4ever

TCO17 Round 1B · 2017-03-31 · by cgy4ever · Math

Show categories

Class Name: CoinConstruction

Return Type: int[]

Method Name: construct

Arg Types: (int)

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.

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 }

1023
Returns: {1, 2, 4, 8, 16, 32, 64, 128, 256, 512 }

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

Coding Area

Language: C++17 · define a public class CoinConstruction with a public method vector<int> construct(int k) · 116 test cases · 2 s / 256 MB per case