Задача F. Марсианская оптимизация

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

В марсианском языке программирования Mars# сложение реализовано функцией sum, принимающей два аргумента и возвращающей их сумму. Реализация требует много памяти для каждого вызова, в связи с чем в марсианских программах часто возникает опасность переполнения стека.

Марсианскому программисту понадобилось посчитать сумму N переменных. Чтобы предотвратить переполнение стека, ему необходимо как можно сильнее уменьшить максимальную глубину вложенных вызовов функции. Помогите запрограммировать оптимальный вызов функции sum.

Математические свойства функции sum сохранены в марсианской реализации, поэтому при вызове можно произвольно менять порядок слагаемых.

Например, для вычисления суммы переменных a b c d e возможны, в частности, следующие варианты вызова функции:

Второй и третий варианты являются оптимальными, так как в них максимальная глубина вложенных вызовов функции минимальна.

В языке Mars# длина имён переменных составляет от одного до восьми символов. Имена переменных состоят из латинских букв.

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

В первой строке входного файла содержится число N. В следующих далее N строках содержатся имена переменных.

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

В выходном файле должна содержаться единственная строка — сгенерированный вызов функции sum, записанный без пробелов.

Аргументы в вызове функции заключаются в круглые скобки '(' (ASCII 40) и ')' (ASCII 41) и разделяются единственным символом ',' (ASCII 44).

Если существует несколько оптимальных решений, вывести любое из них.

Ограничения

2 ≤ N ≤ 105

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
a
b
z
x
y
sum(z,sum(sum(b,x),sum(y,a)))
2
6
a
bb
ccc
p
qq
rrr
sum(sum(sum(a,p),sum(bb,qq)),sum(ccc,rrr))

Разбор

В данной задаче требуется построить бинарное дерево минимальной высоты, зная количество листьев. Для любого дерева справедливо утверждение: высота дерева равна максимальной высоте его поддеревьев с корнями в узлах единичной глубины плюс один. Минимальная высота дерева монотонно зависит от количества листьев, следовательно нам нужно минимизировать количество листьев одновременно в левом и правом поддеревьях. Таким образом, необходимо минимизировать max(a, n-a), который равен (n+1)/2.

Фрагмент исходного кода:

procedure WriteFunc(l, r: integer);
var q: integer;
begin
  if l = r then
    write(fo, a[l])
  else
    begin
      q := (l+r) shr 1; //q := (l+r) div 2;
      write(fo, 'sum(');
      WriteFunc(l, q);
      write(fo, ',');
      WriteFunc(q+1, r);
      write(fo, ')');
    end;
end;
<>
WriteFunc(1, n);


0.072s 0.008s 13