| Автор: | XIII командный чемпионат школьников Санкт-Петербурга по программированию | Ограничение времени: | 2 сек | |
| Входной файл: | tester.in | Ограничение памяти: | 32 Мб | |
| Выходной файл: | tester.out |
На старости лет один профессор загорелся идеей исследования на прочность транзисторов "КД521(2)". К сожалению, ему не удалось привлечь на помощь никого из коллег, поэтому проводить измерения придется самостоятельно. Но это не пугает профессора.
В шкафу профессор обнаружил m транзисторов данной модели, оставшихся со старых времен, и решил использовать их для экспериментов.
После некоторых размышлений был выбран следующий способ проведения измерений: профессор собирается, перемещаясь по пожарной лестнице, сбрасывать транзисторы с различных этажей. Таким образом он планирует определить, при падении с какого минимального этажа транзистор разбивается. При этом профессор уверен, что транзистор не может выдержать падение с последнего этажа, однако падение с высоты человеческого роста (то есть когда профессор находится на первом этаже) не причиняет транзистору вреда.
Известно, что все транзисторы абсолютно одинаковые, и если транзистор разбивается при падении с некоторого этажа, то он разбивается и при падении со всех этажей с большим номером.
Разбившиеся транзисторы снова использовать нельзя, а если транзистор остался целым после падения, его можно использовать повторно. Для того, чтобы поднять оставшийся целым транзистор, профессору надо спуститься на первый этаж. Оказавшись на первом этаже, профессор может поднять все лежащие там транзисторы.
Годы профессора уже дают о себе знать, поэтому он хочет минимизировать суммарное расстояние, которое ему придется подниматься по лестнице. Но, возраст дает и определенные преимущества — сняв очки, профессор может с любого этажа определить, разбился транзистор или нет.
Изначально профессор находится на первом этаже, и у него имеется m транзисторов. В доме, в котором живет профессор, n этажей.
Найдите минимальное число этажей, которое профессору в худшем случае придется подниматься вверх по лестнице во время проведения экспериментов.
В первом из приведенных примеров оптимальное поведение профессора следующее. Сначала следует подняться на два этажа и бросить транзистор с третьего. Если транзистор разобьется, то следует спуститься на второй этаж и попытаться бросить транзистор оттуда — если транзистор разбивается и при бросании со второго этажа, то результат 2, иначе — 3. Если же транзистор не разобьется при падении с третьего этажа, то придется подняться на четвертый и бросить транзистор оттуда. Если он разобьется, то результат 4, если нет — 5. В худшем случае придется подняться на три этажа.
Во втором примере ничего бросать не надо, результат исследования — 2.
| № | Входной файл (tester.in) |
Выходной файл (tester.out) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|