Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1017. Марсианская оптимизация
Задачи на построениеОлимпиадные задачи на русском языке
| 03/07/2008 | Лето 2008 дорешивание (10C) |
| 23/07/2008 | Лето 2008 - 10 (C) |
| 16/09/2014 | Занятие 3 (B) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В марсианском языке программирования Mars# сложение реализовано функцией
sum, принимающей два аргумента и возвращающей их сумму.
Реализация требует много памяти для каждого вызова,
в связи с чем в марсианских программах часто возникает опасность переполнения стека.
Марсианскому программисту понадобилось посчитать сумму `N` переменных.
Чтобы предотвратить переполнение стека, ему необходимо
как можно сильнее уменьшить максимальную глубину вложенных вызовов функции.
Помогите запрограммировать оптимальный вызов функции sum.
Математические свойства функции sum сохранены в марсианской реализации,
поэтому при вызове можно произвольно менять порядок слагаемых.
Например, для вычисления суммы переменных a b c d e возможны, в частности,
следующие варианты вызова функции:
sum(c,sum(e,sum(a,sum(d,b))))
sum(b,sum(sum(d,a),sum(c,e)))
sum(sum(sum(d,e),b),sum(c,a))
Второй и третий варианты являются оптимальными, так как в них максимальная
глубина вложенных вызовов функции минимальна.
В языке Mars# длина имён переменных составляет от одного до восьми символов.
Имена переменных состоят из латинских букв.
Ввод
В первой строке входного файла содержится число `N`.
В следующих далее `N` строках содержатся имена переменных.
Вывод
В выходном файле должна содержаться единственная строка – сгенерированный
вызов функции sum, записанный без пробелов.
Аргументы в вызове функции заключаются в круглые скобки
'(' (ASCII 40) и ')' (ASCII 41) и
разделяются единственным символом ',' (ASCII 44).
Если существует несколько оптимальных решений, вывести любое из них.
Ограничения
`2\ ≤\ N\ ≤\ 10^5`
Пример ввода 1
5 a b z x y
Пример вывода 1
sum(z,sum(sum(b,x),sum(y,a)))
Пример ввода 2
6 a bb ccc p qq rrr
Пример вывода 2
sum(sum(sum(a,p),sum(bb,qq)),sum(ccc,rrr))
