Informacje dla kandydatów

Łamigłówka arytmetyczna

Między liczbami wstawić operacje arytmetyczne +, -, *, / oraz nawiasy aby otrzymać zadaną wartość:
$$\begin{array}{rcl}
1 \; 2 \; 3 \; 4 \; 5 \; 6 \; 7 \; 8 \; 9 & = & 1 \\
1 \; 2 \; 3 \; 4 \; 5 \; 6 \; 7 \; 8 \; 9 & = & 10 \\
1 \; 2 \; 3 \; 4 \; 5 \; 6 \; 7 \; 8 \; 9 & = & 100 \\
1 \; 2 \; 3 \; 4 \; 5 \; 6 \; 7 \; 8 \; 9 & = & 1000
\end{array}$$

Przykładowe rozwiązania:
$$\begin{array}{rcl}
1 + 2 + 3 + 4 + 5 - ( 6 + 7 ) + 8 - 9 & = & 1\\
1 + 2 + 3 + 4 + 5 * ( 6 - ( 7 + 8 ) + 9 ) & = & 10\\
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 * 9 & = & 100\\
1 + 2 * ( ( 3 * ( 4 + 5 ) + 6 ) * ( 7 + 8 ) ) + 9 & = & 1000\\
\end{array}$$

Nie da się jednak w taki sposób z cyfr 1, 2, 3, 4, 5, 6, 7, 8, 9 uzyskać wartość 10000. Z tego powodu dopuścimy sklejanie sąsiadujących liczb (np. cyfry 1 2 można skleić w liczbę 12 a cyfry 1 2 3 w liczbę 123).

Dopuszczając sklejanie sąsiednich liczb znajdź rozwiązanie dla:
$$\begin{array}{rcl}
1 \; 2 \; 3 \; 4 \; 5 \; 6 \; 7 \; 8 \; 9 & = & 10000
\end{array}$$

Wskazówka: Napisz program, który tworzy w sposób systematyczny drzewa wyrażeń. W liściach tych drzew znajdują się zadane liczby (lub liczby będące sklejeniem sąsiednich liczb) a w wierzchołkach wewnętrznych znajdują się operacje +, -, * i /.