Максимальная высота
(Время: 1 сек. Память: 32 Мб Сложность: 63%)
Дано N целых чисел, не превышающих по модулю 105. Необходимо выбрать из этих чисел положительные числа, из которых можно построить максимальной высоты треугольник. То есть на вершине будет одно число, ниже два числа, ниже три числа и т.д. Но для построения есть несколько условий:
- любое число вышестоящего уровня должно быть меньше любого числа нижестоящего уровня;
- любое число текущего уровня должно без остатка делиться на номер уровня (нумерация уровней начинается с вершины треугольника и начинается с единицы);
- числа одного уровня должны быть расположены в порядке неубывания.
Входные данные
В первой строке входного файл INPUT.TXT задано одно число N - количество чисел. Вторая строка содержит N целых чисел, записанных через пробел. (1 ≤ N ≤ 105; |ai| ≤ 105). Гарантируется, что среди всех чисел есть хотя бы одно положительное число.
Выходные данные
В выходной файл OUTPUT.TXT выведите треугольник в виде лесенки (в первой строке одно число, во второй два числа и т.д.). Если возможно построить несколько треугольников максимальной высоты, то необходимо выбрать тот, который будет с минимальной суммой всех чисел.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 15
2 -6 8 6 4 1 9 12 24 28 56 80 -10 12 0 | 1
2 4
6 9 12
24 28 56 80 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
