eolymp
bolt
Try our new interface for solving problems
Məsələlər

Обезьяна и кокосы

Обезьяна и кокосы

Zaman məhdudiyyəti 0.5 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Чтобы разбить кокос, обезьяны обычно забираются на крышу N-этажного дома и бросают кокос вниз. Однажды одна смышленая обезьяна, которой надоело постоянно подниматься на крышу, решила выяснить самый низкий этаж, при бросании с которого кокос разбивается. Обезьяна может подняться на любой этаж с 1-го по N-й (крыша считается (N+1)-м этажом) и бросить кокос в окно. Если кокос при падении не разбивается, обезьяна может использовать его для экспериментов снова. Всего у обезьяны для опытов приготовлено K кокосов. Обезьяна должна выяснить номер искомого этажа, использовав не более K кокосов. Также обезьяна хочет найти этаж за минимальное число бросков, так как она может нести только один кокос и для каждого броска ей приходится спускаться вниз на землю за приготовленным для опытов кокосом или за ранее брошенным, но неразбившимся кокосом.

Напишите программу, которая составит план проведения экспериментов, минимизирующий число бросков в худшем случае. План должен учитывать, что искомым этажом может оказаться любой этаж с 1 по N, а может оказаться, что кокос разбивается только при падении с крыши.

Giriş verilənləri

В первой строке входного файла содержатся два целых числа, разделенных пробелом – количество этажей в доме N (1  ≤  N  ≤  1000000) и число кокосов K (1K1000).

Çıxış verilənləri

В первой строке выходного файла вывести одно целое число – минимальное число испытаний в худшем случае.

Nümunə

Giriş verilənləri #1
10 2
Çıxış verilənləri #1
4