Так как Кассандра еще слишком маленькая, чтобы водить машину, она перемещается по Готэму на общественном транспорте. На билетиках, которые выдают в общественном транспорте, пишут $$$6$$$ цифр — его номер. Чтобы скоротать время поездки, Кассандра часто играет в такую игру: она пытается расставить между цифрами из номера билетика арифметические операции и скобки таким образом, чтобы в результате получилось выражение, равное $$$100$$$. При этом, цифры, между которыми не вставили никакие операции и скобки, склеиваются в одно число. У Кассандры есть несколько правил:
Формально, выражение, которое Кассандра может получить, должно удовлетворять следующей грамматике:
Вот примеры некоторых корректных выражений, а также числа, которым они равны: 2*(3+4) $$$= 14$$$, 0+0 $$$= 0$$$, -{}-239-{}-179 $$$= (-(-239)) - (-179) = 239 + 179 = 418$$$, (17+13)/6 $$$= 5$$$, 0/10 $$$= 0$$$ (ноль делить можно), -(21+12) $$$= -33$$$, (((8))*(9)) $$$= 72$$$.
Вот примеры некоторых некорректных выражений: 2(3+4), 2**2, -239-179-, 17+13/6 (потому что $$$13$$$ не делится на $$$6$$$ нацело), 10/0 (на ноль делить нельзя), 0/0 (даже так), 1+().
Касссандра просит вас помочь ей найти такие выражения для всех возможных номеров билетов. Она понимает, что у вас может не получиться найти выражения для всех номеров. А для некоторых номеров таких выражений и вовсе не существует. Однако, чем больше будет номеров, для которых вы найдете искомые выражения, тем лучше.
Входные данные состоят из нескольких строк. В каждой строке даны $$$6$$$ цифр — номер билета.
Для каждого номера билета выведите искомое выражение, либо «No solution», если такого выражения не существует или вы не смогли его найти.
В этой задаче всего один тест, кроме примера. В нем перечислены все номера билетов в порядке возрастания. Для каждого номера вы должны вывести корректное выражение либо строку «No solution». В противном случае, вы получите $$$0$$$ баллов.
Если формат вывода корректен, ваша посылка будет оценена исходя из количества номеров, для которых вы нашли требуемое выражение. Пусть вы нашли выражения для $$$x$$$ номеров. Обозначим за $$$T$$$ количество номеров, для которых такое выражение существует. Баллы за посылку равны $$$\lfloor score(x) \rfloor$$$, $$$score$$$ — кусочно-линейная функция, точками излома которой являются точки $$$(0, 0)$$$, $$$(5, 5)$$$, $$$(55, 10)$$$, $$$(555, 15)$$$, $$$(5555, 20)$$$, $$$(55555, 25)$$$, $$$(T - 55555, 75)$$$, $$$(T - 5555, 80)$$$, $$$(T - 555, 85)$$$, $$$(T - 55, 90)$$$, $$$(T - 5, 95)$$$, $$$(T, 100)$$$.
Формально $$$score(x)$$$ может быть вычислен следующим образом:
| $$$x$$$ | $$$score(x)$$$ | |
| $$$0 \le x | lt; 5$$$ | $$$x$$$ |
| $$$5 \le x | lt; 55$$$ | $$$5 + \frac{x - 5}{10}$$$ |
| $$$55 \le x | lt; 555$$$ | $$$10 + \frac{x - 55}{100}$$$ |
| $$$555 \le x | lt; 5\,555$$$ | $$$15 + \frac{x - 555}{1\,000}$$$ |
| $$$5\,555 \le x | lt; 55\,555$$$ | $$$20 + \frac{x - 5\,555}{10\,000}$$$ |
| $$$55\,555 \le x | lt; T - 55\,555$$$ | $$$25 + 50 \cdot \frac{x - 55\,555}{T - 55\,555 \cdot 2}$$$ |
| $$$T - 55\,555 \le x | lt; T - 5\,555$$$ | $$$75 + \frac{x - (T - 55\,555)}{10\,000}$$$ |
| $$$T - 5\,555 \le x | lt; T - 555$$$ | $$$80 + \frac{x - (T - 5\,555)}{1\,000}$$$ |
| $$$T - 555 \le x | lt; T - 55$$$ | $$$85 + \frac{x - (T - 555)}{100}$$$ |
| $$$T - 55 \le x | lt; T - 5$$$ | $$$90 + \frac{x - (T - 55)}{10}$$$ |
| $$$T - 5 \le x \le T$$$ | $$$95 + (x - (T - 5))$$$ |
123456 987654 111111 000000 001000
1+(2+3+4)*(5+6) 9+87+(6-5)*4 (111-11)/1 No solution 0+0+100+0
