Обезьяна и кокосы
Чтобы разбить кокос, обезьяны обычно забираются на крышу n-этажного дома и бросают кокос вниз. Однажды одна смышленая обезьяна, которой надоело постоянно подниматься на крышу, решила выяснить самый низкий этаж, при бросании с которого кокос разбивается. Обезьяна может подняться на любой этаж с 1-го по n-й (крыша считается (n+1)-м этажом) и бросить кокос в окно. Если кокос при падении не разбивается, обезьяна может использовать его для экспериментов снова. Всего у обезьяны для опытов приготовлено k кокосов. Обезьяна должна выяснить номер искомого этажа, использовав не более k кокосов. Также обезьяна хочет найти этаж за минимальное число бросков, так как она может нести только один кокос и для каждого броска ей приходится спускаться вниз на землю за приготовленным для опытов кокосом или за ранее брошенным, но неразбившимся кокосом.
Напишите программу, которая составит план проведения экспериментов, минимизирующий число бросков в худшем случае. План должен учитывать, что искомым этажом может оказаться любой этаж с 1 по n, а может оказаться, что кокос разбивается только при падении с крыши.
Входные данные
В первой строке содержатся два целых числа, разделенных пробелом – количество этажей в доме n (1 ≤ n ≤ 1000000) и число кокосов k (1 ≤ k ≤ 1000).
Выходные данные
Вывести минимальное число испытаний в худшем случае.