Задача D. Башня из банок ≡
| Автор: | Завгороднев А.А. | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
Условие
Программист Петя очень любит математику и газированные напитки. И однажды ночью он решил построить башню из имеющихся у него N банок, взявшись за это с математической точки зрения.
Петя считает, что у каждой банки есть нестабильность, и если эта характеристика больше m, то банка падает.
Петя придумал стратегию расстановки: если ставить одну банку прямо на предыдущую, то ее нестабильность рассчитывается как нестабильность нижестоящей, умноженная на k2.
А если ставить банки пирамидой, то есть каждую следующую ставить на две предыдущие, то нестабильность рассчитывается как нестабильность нижестоящей, умноженная на k.
Если поставить банку на пол, то ее нестабильность равна единице.
Требуется узнать, башню какой максимальной высоты может построить Петя.
Формат входных данных
Входной файл содержит три целых числа N, k и m.
Формат выходных данных
Выходной файл должен содержать единственное целое число - высоту башни.
Ограничения
0 < N ≤ 109
1 < k ≤ 104
1 < m ≤ 109
Описание системы оценивания
| Подзадача | Ограничения | Баллы |
|---|---|---|
| 1 | N, k, m < 50 | 10 |
| 2 | N, k, m < 2 * 103 | 20 |
| 3 | N, k, m < 2 * 104 | 20 |
| 4 | N, k, m < 2 * 105 | 20 |
| 5 | N, k, m < 2 * 106 | 10 |
| 6 | нет | 20 |
Примеры тестов
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|