DesChiffres | Topcoder Archive

Problem Statement

The time limit for this problem is 4 seconds.

Des chiffres et des lettres (Numbers & Letters) is a French game show in which the contestants have to solve puzzles that involve numbers and letters. Countdown is the equally famous British adaptation of this game show. This problem is about the "numbers game" from these game shows.

There are 24 tiles with numbers. Four of them contain "big numbers": 25, 50, 75, 100. The remaining twenty contain "small numbers": two copies of each of the numbers 1 through 10.

The game is played using six of these tiles and a target. The target is an integer between 100 and 999, inclusive.

Each of the contestants is trying to produce an arithmetic expression that evaluates to the given target (or at least to a value that is as close to the target as possible).

The expression must obey the following rules:

The expression must only consist of the provided number tiles, parentheses, and the binary operations +, -, * and /.
Only integer division (without remainder) is allowed. For example, (2*3)/6 is allowed but (2/6)*3 is not. Obviously, you cannot divide by zero.
Each tile must be used as a separate number. It is not allowed to create bigger numbers by concatenating tiles. (E.g., you cannot use the tiles 2 and 3 as the number 23.)
You are not required to use all tiles, you can select any non-empty subset of them.
Each tile can only be used at most once. (E.g., if you have two tiles with a 7, your expression cannot contain three or more 7s.)

Given the int[] tiles with the numbers on the tiles and the int target, find and return the best value that can be constructed. I.e., find and return an integer X such that X can be constructed from the tiles and abs(X-target) is minimized. If there are two possible return values, return the smaller one of them.

Definition

Class:: DesChiffres
Method:: solve
Parameters:: int[], int
Returns:: int
Method signature:: int solve(int[] tiles, int target)
(be sure your method is public)

Notes

Using a unary minus is not allowed. (It isn't really useful anyway, if we were to allow it, it would not change the return value in any test case.)

Constraints

tiles will contain exactly 6 elements.
tiles will contain six of the 24 tiles mentioned in the statement.
target will be between 100 and 999, inclusive.

Examples

```
{1,2,3,4,5,6}
```
```
722
```
```
Returns: 722
```
This target can be achieved: 722 = (6*5*4*3+1)*2.
```
{100, 9, 9, 4, 5, 8}
```
```
734
```
```
Returns: 733
```
The target 734 cannot be produced from these tiles, but 733 can and thus it is a valid answer. We have 733 = (100 - 9) * 8 + 9 - 4. Note that this solution does not use the tile 5. Also note that due to the tiebreaker rule only 733 is a valid answer, even though 735 can also be constructed.
```
{100, 50, 75, 25, 4, 7}
```
```
100
```
```
Returns: 100
```
Sometimes the game is really easy. Here we can just use the tile 100 and we are done.
```
{100, 50, 4, 4, 2, 2}
```
```
128
```
```
Returns: 128
```
One way to produce 128 is (100/50)*2*2*4*4. Another way is (50/2)+(4/4)+2+100.
```
{5,2,3,1,9,4}
```
```
999
```
```
Returns: 1000
```
The value X you construct is not required to lie in the range [100,999]. In this case, 998 and 999 are impossible but 1000 can be constructed as (9+1)*4*5*(2+3).
```
{1,10,4,3,1,3}
```
```
900
```
```
Returns: 720
```
Sometimes the best answer is far from the target. In this case the biggest value we can actually produce is 720 = 10 * 4 * 3 * 3 * (1+1).

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.