SameAmount | Topcoder Archive

Problem Statement

You have an infinite number of coins of several different types of currency. You are given the relative value of each type of coin in the int[] currencyCosts. Each element represents the value of a single coin of one type expressed in US cents. For example, if currencyCosts = {1, 17, 5}, then each coin of the first type is worth 1 US cent, each coin of the second type is worth 17 US cents, and each coin of the third type is worth 5 US cents.

You are also given a int[] values, where each element represents a count. Your task is to assign a type of coin to each of the counts. For each count, you must then place that many coins of the chosen type in a separate pile. The value in US cents of each pile must be equal. For example, if values = {221, 65}, you could assign the third type of coin to 221 and the second type of coin to 65. You would then have a pile of 221 coins of the third type, worth 221 * 5 = 1,105 US cents, and a pile of 65 coins of the second type, worth 65 * 17 = 1,105 US cents.

If it is possible to achieve this goal, return a int[] containing the same number of elements as values, where the i-th element is the 0-based index of the coin type to assign to the i-th element of values. If there are multiple possible assignments, return the one that comes earliest lexicographically. A int[] A1 comes before a int[] A2 lexicographically if A1 contains a smaller element at the first index where they differ. If there are no possible assignments, return an empty int[] instead.

Definition

Class:: SameAmount
Method:: assign
Parameters:: int[], int[]
Returns:: int[]
Method signature:: int[] assign(int[] currencyCosts, int[] values)
(be sure your method is public)

Notes

One type of coin can be assigned to multiple elements of values.

Constraints

currencyCosts will contain between 1 and 50 elements, inclusive.
Each element of currencyCosts will be between 1 and 1000, inclusive.
values will contain between 1 and 50 elements, inclusive.
Each element of values will be between 1 and 1000, inclusive.

Examples

```
{1, 17, 5}
```
```
{221, 65}
```
```
Returns: {2, 1 }
```
Example from the problem statement.
```
{1}
```
```
{2, 5}
```
```
Returns: { }
```
There is no possible assignment at all.
```
{7, 7, 8}
```
```
{13}
```
```
Returns: {0 }
```
There is only one value, so assigning any type of coin to the value is possible. However, assigning the first one leads to the lexicographically smallest solution.
```
{12, 6, 43, 18, 19, 25, 2}
```
```
{36, 57, 114, 36, 342}
```
```
Returns: {4, 0, 1, 4, 6 }
```
Note that the same type of coin is assigned to both the first and fourth element of values.

{9, 72, 541, 10, 19, 34, 123, 333, 98, 56, 43}

{19, 18, 14, 100, 999, 1000, 10, 55, 66, 77, 21, 18, 19, 13, 7, 87, 91, 102}

Returns: { }

```
{6, 8, 3, 4}
```
```
{24, 32}
```
```
Returns: {1, 0 }
```
Assign the second type of coin to the first count, and assign the first type of coin to the second count. Each pile will then be worth 192 US cents. Note that the assignment {3, 2} would also lead to each pile having the same value, but we choose {1, 0} instead because it comes first lexicographically.

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.