Дан автобусный билет с номером, состоящим из N цифр. Расставить между цифрами знаки арифметических операций ('+', '-', '/', '*') и скобки таким образом, чтобы значение полученного выражение было равно 100. Можно образовывать многозначные числа из стоящих рядом цифр.

Выражение должно быть корректным с точки зрения арифметики. Допустимы лишние скобки, не нарушающие корректности выражения.

Требуется написать программу, решающую эту задачу.

Знаки операций означают:

• '+' сложение;
• '-' вычитание (унарный минус не допускается!);
• '*' умножение;
• '/' деление нацело;

Используется стандантный приоритет операций, т.е. выражение 6*5/7+5-1/3 интерпретируется как ((((6*5)/7)+5)-(1/3))

Число цифр N в номере билета не больше 6.

При возникновении затруднений в решении задачи допустимо частное решение, использующее не все знаки арифметических действий и/или скобки.

Программа вводит номер с клавиатуры с приглашением

Номер: 

0+(19+1)*5+0=100 

123456=? 

Предполагается, что все вводимые данные корректны

Система оценки

1. Организация диалога с пользователем 2 балла
2. Полное решение 33 балла
3. Частные решения:
   • не используется '/' 28 баллов
   • не используется '*', '/' 10 баллов
   • не используются скобки 11 баллов
   • не используется скобки и '/' 10 баллов
   • не используется скобки, '*' и '/' 5 баллов
4. Удаление из выражения лишних скобок 5 баллов