Задача
Мама испекла Серёже на день рождения большой и вкусный круглый торт и поручила ему самому его разрезать. У него в распоряжении есть достаточно длинный нож, позволяющий делать разрез по всему торту, однако так как общение с режущими инструментами всегда таит в себе определенные опасности, Серёжа хочет сделать минимальное количество разрезов так, чтобы всем гостям досталось хотя бы по одному кусочку. Естественно, при этом он должен не забыть, что и ему должен за праздничным столом достаться хотя бы один кусочек маминого торта, но при этом Серёжу абсолютно не интересует, какого размера и формы будут куски торта – для него главное, чтобы они все имели такую же толщину, как и испеченный мамой торт.
Учтите, что гостей к Серёже может придти достаточно много.
Входные данные
Одно число – количество гостей $n$ $(n < 210000001)$.
Выходные данные
Искомое количество разрезов $k$.
Тесты
№ |
Входные данные |
Выходные данные |
| 1 |
3
|
2 |
| 2 | 0 | 0 |
| 3 | 120 | 15 |
| 4 | 210000000 | 20494 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 |
#include <iostream> #include <cmath> using namespace std; int main() { int n; cin >> n; cout << round(sqrt(2 * n)); return 0; } |
Решение
Максимального количества кусков можно достичь в том случае, когда каждый новый разрез будет пересекать все предыдущие. Таким образом новым $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