Hide

# Countdown

The “Countdown” TV show has a part that consists of obtaining a number by combining six different numbers using the basic mathematical operations: addition, subtraction, product and division. The basic rules for the game are:

• The contestant selects six of twenty-four shuffled tiles. The tiles are arranged into two groups: four “large numbers” ($25$, $50$, $75$ and $100$) and the remainder “small numbers”, which comprise two each of the numbers $1$ to $10$. Hence the tiles have the values $\{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25, 50, 75, 100\}$.

• The contestants then have thirty seconds to get a number as close to the target as possible by combining the six selected numbers using addition, subtraction, multiplication and division.

• Not all numbers need to be used.

• A number can be used only as many times as it appears.

• Fractions are not allowed, only positive integers may be used at any stage of the calculation.

Example:

• Contestant requests two large numbers and four small numbers.

• Selection is: $\{ 75, 50, 2, 3, 8, 7\}$

• Randomly generated target is: $812$

• Contestant declares result: $813$

• Contestant gives details: $75 + 50 = 125$; $125 - 8 = 117$; $117 \cdot 7 = 819$; $3 \cdot 2 = 6$; $819 - 6 = 813$

• Expert notes: $50 + 8 = 58$; $7 \cdot 2 = 14$; $14 \cdot 58 = 812$

Your task is to write a program that calculates the best sequence of operations that lead to the target number $T$. If there is no way to get $T$, give the closest solution.

## Input

The input consists of several cases, one per line. The first line indicates the number of cases to process ($1 \leq C \leq 5$). Each of the following $C$ lines contains six natural numbers from the set $\{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25, 50, 75, 100\}$ and another natural number $T$ ($1 \leq T \leq 999$) that indicates the target.

## Output

The output for each case will be a set of lines with the following format:

• First line: Target: number $T$

• $n$ lines: sequence of operations, the format is $\mathtt{operand_1\; operator\; operand_2 = result}$

• Last line: Best approx: number obtained

• Blank line

See example for a better understanding. If there is more than one best approximation, all of them will be considered valid. The sequence of operations should be valid, you should never use a value before you obtain it. It is OK to print more operations than needed as long as they are valid. Note that all the numbers and operators must be separated by at least one space.

Sample Input 1 Sample Output 1
3
1 75 100 5 3 25 25
100 100 100 100 100 75 345
1 3 1 10 100 75 345

Target: 25
Best approx: 25

Target: 345
100 + 100 = 200
75 + 100 = 175
200 * 175 = 35000
35000 - 100 = 34900
34900 / 100 = 349
Best approx: 349

Target: 345
100 - 10 = 90
3 * 90 = 270
270 + 75 = 345
Best approx: 345


CPU Time limit 3 seconds
Memory limit 1024 MB
Difficulty 4.3medium
Statistics Show