beecrowd | 1395

Numbers and Operations

By Ginés García Mateos, UM Spain
Timelimit: 5

We want to solve the classical problem of obtaining a given target number starting from a set of initial numbers according to the following rules:

We shall make the following assumptions on the input data:

In order to make unique the solution provided by the program, we shall also make the following assumptions on the solution that we will consider as correct: The program should provide the solution that reaches the target in the minimum number of operations. If there is more than one solution with the minimum number of operations, we will decide which one to take according to the characteristics of the first operation in which they differ. The next rules will apply.


The input consists of a set of lines. Each line represents a test case, and it will be given in the following format:

T N I1 ... IN

T is the target number, N is the number of initial numbers, and I1 ... IN are the initial numbers themselves. All numbers are separated by a single blank space. There will be no trailing/leading blank spaces at the beginning/end of any input line. A final line with a single zero marks the end of the input. This last line must not be processed.


For each input case (input line), the program should produce a line with the message:

No solution

if the target number cannot be obtained from the initial numbers, or a set of lines with the sequence of operations that leads from the initial numbers to the target, taking into consideration the previous criteria. Each operation must be expressed in the following format:

left_operand operator right_operand = result

where left_operand and right_operand represent the numbers involved in the operation, result is the result of the operation, and operator is a single character that represents the operation carried out, and it must be taken from the following ones:

'+' : addition
'x' : multiplication
'-' : subtraction
'/' : division

For each input case, the last line of its solution must end with a '<-' symbol, indicating that this is the last operation that gives the target number as result. In all cases, there must be one blank space (and only one) between each printed item and the following one. There should be no leading/trading blank spaces at the beginning/end of any output line. Each line must end with an end of line mark, and there should appear no blank lines at the output.

Sample Input Sample Output

811 6 7 15 19 25 2 3
911 6 1 2 3 4 5 6
1897 7 33 2 11 25 7 17 13
911 7 7 11 23 27 17 7 2

15 + 7 = 22
22 x 19 = 418
418 x 2 = 836
836 - 25 = 811 <-
No solution
25 x 2 = 50
17 x 13 = 221
221 + 50 = 271
271 x 7 = 1897 <-
23 + 11 = 34
34 x 27 = 918
918 - 7 = 911 <-