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

Условие

В марсианском языке программирования 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
a
b
z
x
y

sum(z,sum(sum(b,x),sum(y,a)))

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);