Задача
Мама испекла Серёже на день рождения большой и вкусный круглый торт и поручила ему самому его разрезать. У него в распоряжении есть достаточно длинный нож, позволяющий делать разрез по всему торту, однако так как общение с режущими инструментами всегда таит в себе определенные опасности, Серёжа хочет сделать минимальное количество разрезов так, чтобы всем гостям досталось хотя бы по одному кусочку. Естественно, при этом он должен не забыть, что и ему должен за праздничным столом достаться хотя бы один кусочек маминого торта, но при этом Серёжу абсолютно не интересует, какого размера и формы будут куски торта – для него главное, чтобы они все имели такую же толщину, как и испеченный мамой торт.
Учтите, что гостей к Серёже может придти достаточно много.
Входные данные
Одно число – количество гостей 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 значит общее количество кусочков для гостей вычисляется как сумма арифметической прогрессии n=i2+k2. Тогда k=⌈−1+√1+8n2⌉.
Эту формулу немного можно упростить, в результате получим k=[√2n]
Ссылки
Условие задачи e-olymp
Код решения ideone