0265. 1 3 4 6

Имя входного файла:	numbers.in
Имя выходного файла:	numbers.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

На первом курсе математического факультета есть такой курс: "Алгебра и теория чисел". Раз теория чисел, то должны встречаться числа. А так как студенты этот курс изучают, то задачи с числами они тоже должны уметь решать. И вот, один раз появилась задача такого вида: даны числа 1, 3, 4 и 6. Необходимо расставляя арифметические операции, скобки и возможно, переставляя цифры получить выражение, равное 24. При этом обязательно использовать все данные числа (иначе неинтересно). Само собой, нельзя эти числа склеивать (т. е. из 1 и 4 получить 14). Студенты очень долго думали над этой задачей, но все таки ее решили. Но хорошего студента отличает тяга к исследованиям и экспериментам. Так вот, студенты задумались: а если у нас есть какой-то набор чисел и арифметических операций, то что вообще можно из этого получить. Но ведь различных выражений слишком много, поэтому студенты решили, что на бумаге вручную решать эту задачу будет очень сложно, долго, да и некогда (сессия она того... приближается... готовиться надо... то-се...). Поэтому написать программу для решения такой задачи попросили Вас. Вам ведь нетрудно.

Формат входного файла

Входной файл состоит из одной строки. В ней сначала записаны от 2 до 4-х цифр - это числа от 0 до 9, которые можно использовать (все числа одно-цифровые). Далее от 1 до 4-х знаков арифметических операций (+, -, *, /). Перечисленные операции использовать можно, остальные - нет. Далее может быть (а может и не быть) записан символ "s". Если он есть, это означает, что числа можно переставлять (брать в любом порядке). В противном случае в выражении они должны стоять ровно в том порядке, в каком даны во входном файле. Обязательно использовать все числа. Ни в коем случае нельзя склеивать цифры. Пробелов во входном файле нет. В процессе вычисления выражения никогда не должно быть деления на ноль.

Формат выходного файла

Выходной файл должен содержать ровно 101 строку. В k-ой строке должен быть записан способ получения числа k-1. Если это число получить никак нельзя, то должна быть фраза "There is no way to get K.", где K - число, которое нельзя получить. Формат ответа должен удовлетворять следующим условиям:

1. У каждой операции +, -, * или / левое и правое выражение берутся в скобки, за исключением случая, когда выражение - одно число.
2. Если арифметических выражений, равных числу K и удовлетворяющих первому правилу, несколько, то ответом будет максимальное из них, если сравнивать строки этих выражений слева направо. ("abc" как строчка меньше "baa").

В остальном формат должен соответствовать примеру.

Пример:

numbers.in	numbers.out
111+-*s	(1-(1*1))=0 (1-(1-1))=1 (1+(1*1))=2 (1+(1+1))=3 There is no way to get 4. There is no way to get 5. There is no way to get 6. ... There is no way to get 99. There is no way to get 100.

Примечание:

В примере строка ... означает, что все строки с 8-й по 99-ю пропущены, так как они почти совпадают. В ответе Вашей программы должна быть ровно 101 строка.

Источник: Первенство первокурсника ПетрГУ. Осень 2006.

Обсудить       Отправить решение



Версия для печати