Автор: | Жюри всероссийской олимпиады школьников 2010 | Ограничение времени: | 2 сек | |
Входной файл: | gift.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | gift.out | |||
Максимальный балл: | 100 |
Начинающий программист Поликарп очень любит дарить подарки, особенно в коробках. Он давно заметил, что если коробка красиво оформлена, то радость от подарка возрастает многократно. Любой оберточной бумаге он предпочитает клетчатую. В самом деле, после распаковки подарка на ней можно играть в крестики-нолики, морской бой, точки, а также решать задачи и писать программы.
Поликарп очень аккуратен. Он упаковывает подарок в коробку, имеющую форму прямоугольного параллелепипеда, и оклеивает всю ее поверхность клетчатой бумагой. При этом каждая грань коробки представляет собой прямоугольник, состоящий из целых клеток. На рисунке изображен пример такой упаковки подарка.
В настоящий момент Поликарп собирается поздравить свою подругу, недавно вернувшуюся с очередной олимпиады. Он хочет подарить ей подарок в большой и красивой коробке.
У Поликарпа в наличии есть лист клетчатой бумаги, состоящий из n клеток. Каким будет максимальный объем коробки, которую можно оклеить с использованием этого листа бумаги описанным выше способом? Поликарп может разрезать лист клетчатой бумаги по границам клеток произвольным образом и оклеивать коробку получившимися фигурами, поэтому форма листа не важна, а имеет значение только количество клеток на нем. Поликарп может использовать для оклеивания коробки не все клетки.
Напишите программу, которая по заданному количеству клеток n находит размеры коробки максимального возможного объема.
Входной файл содержит одно целое число n (6 ≤ n ≤ 1013) — количество клеток на листе клетчатой бумаги.
Выведите в первую строку выходного файла максимальный объем коробки, которую может подарить Поликарп. Объем следует выводить в «кубических клетках», то есть единицей измерения является куб со стороной равной длине стороны клетки.
Во вторую строку выведите ширину, длину и высоту искомой коробки. Единица измерения — размер клетки. Числа разделяйте пробелами. Если решений несколько, то выведите любое из них.
Решения, корректно работающие при n ≤ 5000, будут оцениваться из 30 баллов, а решения, корректно работающие при n ≤ 108, будут оцениваться из 70 баллов.
№ | Входной файл (gift.in ) |
Выходной файл (gift.out ) |
---|---|---|
1 |
|
|
2 |
|
|