ACM Regional Programming Contest 1997

Problem No. 5 - Evaluating an Equations Board

Equations is a game that is played competitively in several parts (The game as described below is only a subset of the actual game). You are to write a program which evaluates an Equations board.

The game equations is played with 13 cubes. Each cube will contain six of the following symbols, one symbol on each side:

0 1 2 3 4 5 6 7 8 9 + - x

(Each symbol can be found on six of the cubes.) The symbols + ,- , and x stand for the binary operations addition, subtraction, and multiplication, respectively.

There are two sections to an Equation board: Resources and Goal. At the beginning of a game of Equations, all of the cubes are rolled and placed into Resources section. For all examples below, assume that the following was rolled:

0 1 4 5 6 7 9 + + + - x x

One of the players then sets a goal by taking one or two of the digits in the Resources section and placing them into the Goal section. (assume that you cannot have a goal with a leading 0 such as 09.) For all the examples below, the goal is 56.

The central idea of the game is to make a solution which equals the goal and uses a subset of the other cubes. There are two main restrictions to the solution:

  1. it can use only one-digit numbers. For instance, 49 + 7 is not a valid solution, since 49 is a two-digit number.

  2. Parentheses may be used wherever valid in standard arithmetic. This means that 7 x ( 9 - 1) is a valid solution for the above goal, using the aboves cubes. However, the parenteheses cannot be used for implied multiplication, so 7 ( 9 - 1) is not a valid solution.

Your program will read two lines at a time (until end of file) from the input file. This two lines represent the Resource and the Goal sections of an Equations board. There will be no embedded, leading or trailing blanks on each line; you may also assume that the two lines contain only the 13 symbols which are legal symbols in Equations.

For each situation, the program should output "no solution" when you cannot make a solution which equals the goal using some or all cubes from Resources, or should output "solution" when you can make a solution that uses some or all cubes in Resource.

Input file example:


Output file example:

no solution