Продажа деревьев
(Время: 1 сек. Память: 16 Мб Сложность: 25%)
На современном рынке полно разных товаров, в том числе и информационных. Вам представилась великолепная возможность продавать уникальный товар, который не каждый день встретишь на рынке – корневое дерево.
Да! Это именно то, о чем вы сейчас подумали!!! Это неориентированный невзвешенный связный граф без петель и циклов, у которого к тому же имеется корень и листья. Можете считать, что сегодня у вас нет конкурентов, а желающих среди любителей олимпиадного программирования приобрести данный продукт предостаточно.
У вас имеется несколько вершин, из которых вы можете создавать любые корневые деревья: бинарные, сбалансированные (в том числе и красно-черные) и так далее. Учитывайте вкусы покупателей: кому то они нужны для бора, кому то для кучи, а кому и просто для DFS'а. В общем, можете создать как одно, так и целый лес таких деревьев, а потом разом их продать.
Однако также следует учитывать современные реалии, а именно то, что цена корневого – это сумма глубин его листьев. Корень дерева имеет глубину 0, а глубина любой другой вершины равна глубине ее предка плюс один.
Никто не сомневается в ваших способностях, а именно в том, что вы с легкостью по заданному дереву сможете вычислить его стоимость. А умеете ли вы строить дорогие деревья? Сейчас мы это проверим!
По заданному количеству вершин N требуется построить одно или несколько деревьев, имеющих максимальную стоимость.
Входные данные
Входной файл INPUT.TXT содержит целое число N (1 ≤ N ≤ 8 589 934 591) – количество вершин.
Выходные данные
В выходной файл OUTPUT.TXT выведите максимально возможную суммарную цену построенных деревьев.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1 | 0 |
| 2 | 2 | 1 |
| 3 | 3 | 2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
