e-olymp 398. Торт для Серёжи

Задача

prb398Мама испекла Серёже на день рождения большой и вкусный круглый торт и поручила ему самому его разрезать. У него в распоряжении есть достаточно длинный нож, позволяющий делать разрез по всему торту, однако так как общение с режущими инструментами всегда таит в себе определенные опасности, Серёжа хочет сделать минимальное количество разрезов так, чтобы всем гостям досталось хотя бы по одному кусочку. Естественно, при этом он должен не забыть, что и ему должен за праздничным столом достаться хотя бы один кусочек маминого торта, но при этом Серёжу абсолютно не интересует, какого размера и формы будут куски торта – для него главное, чтобы они все имели такую же толщину, как и испеченный мамой торт.

Учтите, что гостей к Серёже может придти достаточно много.

Входные данные

Одно число – количество гостей $n$ $(n < 210000001)$.

Выходные данные

Искомое количество разрезов $k$.

Тесты

Входные данные

Выходные данные

1
3
2
2 0 0
3 120 15
4 210000000 20494

Код программы

Решение

Максимального количества кусков можно достичь в том случае, когда каждый новый разрез будет пересекать все предыдущие. Таким образом новым $k$-ым сечением мы разрежем $k$ кусков торта на две части, а к общему количеству кусочков прибавится ровно $k$ новых. Заметим, что имениннику всегда достанется кусок, который не считается новым. Множество всех новых кусков составит арифметическую прогрессию: $0,1, 2, 3 … k-1, k$ значит общее количество кусочков для гостей вычисляется как сумма арифметической прогрессии $\mathbf{n = \frac{i^{2}+k}{2}}$. Тогда $\mathbf{k =\left \lceil \frac{-1+\sqrt{1+8n}}{2} \right \rceil }$.

Эту формулу немного можно упростить, в результате получим $\mathbf{k =\left [ \sqrt{2n}\right ]}$

Ссылки

Условие задачи e-olymp

Код решения ideone

One thought on “e-olymp 398. Торт для Серёжи

    • Вы специально изуродовали все формулы при помощи \mathbf? Или это кошка так удачно прошла по клавиатуре?Три раза.
    • Определитесь, новый разрез должен пересекать все предыдущие (разрезы?) или все кусочки. Всегда ли существует разрез, который пересекает все кусочки? Как будем резать? Разрезы прямые?
    • «Заметим, что имениннику всегда достанется кусок, который не считается новым». Не новый кусочек? Что вы имеете в виду? Вроде задача распределение кусков между едоками не ставится. Просто кусков должно быть на один больше чем гостей.
    • Если был кусок торта и вы его разрезали. Стало два кусочка. По вашей логике один из них новый? Какой?
    • Разрез это хорда? В условии только намеки
    • Ваше решение опирается на утверждение, что на $k$-м шаге гарантировано можно найти хорду, пересекающую $k$ кусков. Более того, ни для какого шага нет хорды, пересекающей более чем $k$ кусков. Это нужно доказать. Или, по крайней мере, как-то обосновать предложив свой способ разрезания торта.

Добавить комментарий