Несложная логическая задачка

[vak]

Мне тут надысь задачку подсунули, которую я слёту не смог решить. Дано: небоскрёб высотой 100 этажей и две бутылки водки. Требуется определить этаж, с которого бутылка, выброшенная в окно, разбивается. За минимальное количество попыток, естественно.

Есть верные решения от maugletta, trustix, chtovimenitebe, skolk, ircicq, denis_iv. А parovoz и dadv дали общую формулу для N этажей.

spamsink предложил идею решения для N этажей и K бутылок.

Comments

[cema.livejournal.com]

Тут подумать надо, а подумать нету, сплю.

Т.е. я прикинул, но строго думать сейчас не могу. У меня пока получилось не более 17 бросаний для 100 этажей и 2 бутылок, но доказывать оптимальность (или неоптимальность) не стану, устал. Не третий курс, увы.

Рассуждение, пока я спал, было такое. С одной бутылкой и N этажами нужно пробовать этажи 1, 2 и т.д., пока не разобьется, т.е. до N бросаний.

Если две бутылки и 3 этажа, пробуем первую на этаже 2, дальше понятно.

Если две бутылки и 4 этажа, пробуем первую на этаже 2. Если разбилась, вторую на этаже 1; если нет, то имеем задачу "две бутылки, два этажа", только нумерация этажей начинается не с 1, а с 3.

Если две бутылки и N этажей, то первой бутылкой можно пробовать этаж X. Если разбилась, то теперь задача "1 бутылка, X-1 этажей", если нет, то "2 бутылки, N-X этажей". Выписывать рекурсивное определение функции я не буду, потому что сплю и пора бежать. Конечно, на кандидатском минимуме спать нельзя. (Бежать, наверно, можно.)

10, 20, 29, 38, 46, 54, 61, 67, 73, 78, 83, 87, 91, 94, 97, 99, 100.

:)

[vak]

Все правильно. Если процесс развернуть до конца, получится 14 бросаний.

Re: :)

[cema.livejournal.com]

Так это нужно не спать.

(Я вчера специально стал писать ответ, чтобы не заснуть окончательно.)