Опасные эксперименты
Вам дано здание с n этажами и k одинаковыми бутылками. Каждую бутылку можно сбросить с любого этажа здания, и она разобьётся, если сбросить её с некоторого «критического» этажа или выше.
Ваша задача — определить минимальное количество попыток, необходимое, чтобы выяснить самый нижний этаж, при сбрасывании с которого бутылка ломается, используя имеющиеся бутылки.
Входные данные
Единственная строка входных данных содержит два целых числа
n (100 ≤ n ≤ 500) и k (1 ≤ k ≤ 30), обозначающие количество этажей в здании и количество бутылок соответственно.Выходные данные
Выведите одно целое число — это минимальное количество попыток, которое нужно совершить, чтобы определить самый нижний этаж, на котором бутылка начинает разбиваться, имея заданное количество бутылок.
Примеры
Input | Output |
100 2 | 14 |
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB