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

[vak]

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

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

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

Comments

[maugletta.livejournal.com]

Этажи для бросания первой бутылки:
14-й, 27-й, 39-й, 50-й, 60-й, 69-й, 77-й, 84-й, 90-й, 95-й, 99-й

Если при броске с 14 этажа бутылка разбилась- начинаем бережно кидать вторую с 1 этажа. потом со второго и проч.
Так мы определяем- где ж эта сволочь разобьется.

Если при броске с 14 этажа первая бутылка осталась цела -поднимаемся на 27 .
Кидаем.
Если разбилась- начинаем исследовать , кидая вторую бутылку с 15, 16 , 17 ..и т.п.этажа:)
Если не разбилась- поднимаемся на 39.

[ubluzok.livejournal.com]

Кинуть с сотого этажа. точно должна разбиться. А вторую можно и на себя применить

[evgen2.livejournal.com]

С третьего этажа об асфальт - разбивается без всяких небоскрёбов и попыток. "Проверено электроникой" (тм)

[getman.livejournal.com]

Несерьезно как-то, это же самая элементарная задача на бинарный поиск с О(ln).

[spamsink]

OT: Any news on the process?

[vak]

Слишком просто. :)
Надо самый низкий этаж найти.

[vak]

Асфальт не обещан условиями. Может, дом на песке стоит?

[vak]

Не совсем. Нужно найти самый низкий этаж, с которого бутылка бьётся.

[trustix.livejournal.com]

Наибольшее количество попыток – 14 раз.

Вместо того, чтобы разбивать этажи по 10, надо начать с 14-го, затем подняться на 13 этажей, затем на 12, затем на 11, затем 10, 9, 8, 7, 6, 5, 4 до тех пор, пока не дойдёте до 99-го. Если бы яйцо разбилось на 100-ом этаже, получилось бы 12 попыток (или 11, если вы предположите, что яйцо разобьётся на 100-ом этаже). Предположим, для примера, что мы выяснили, что 49-ый — самый верхний этаж, где яйцо не разбилось, тогда наши попытки: 14-ый, 27-ой, 39-ый, 50-ый (яйцо разбилось на 50-ом этаже), плюс 40, 41, 42, 43, 44, 45, 46. 47, 48 и 49 этаж, всего 14 попыток.

где то на википедии есть общее решение для n этажей и m яиц; я скопировал из задачек гугла для соискателей

[vak]

Тормоза эти юристы. К концу прошлой недели обещали наконец зафайлить visa application.

[getman.livejournal.com]

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

[vak]

Сто попыток? Или сразу с сотого швырнуть?

[mr-tottor.livejournal.com]

кинуть с 50-ого. разбилась - с 25. не разбилась - с 75. и так, методом последовательного приближения пока не найдем точно. Но двух бутылок не хватит. Штук 7-8 надо(на вскидку).

[cema.livejournal.com]

Задачу я помню, а решение не помню.

[chtovimenitebe.livejournal.com]

min x, where x(x+1)/2>100
x=14

[maria-tuzhilina.livejournal.com]

Я знаю. Идти вверх и кидать последовательно с каждого этажа. Тогда и одной бутылки хватит. Второй можно отметить какой-нибудь момент, типа середины, чтобы не все этажи перебирать.

[golosptic.livejournal.com]

А сколько у нас бутылок для тестирования?

[tnt23.livejournal.com]

Выкидываем первую бутылку водки с каждого четного (2, 4 и так далее) этажа до тех пор, пока она не раскокается. Вторую бутылку используем для уточнения результата, выкинув этажом ниже.

[http://users.livejournal.com/_slw/]

с первого с размаху херакнуть об асфальт.
если асфальта нет -- о стену небоскреба.
в условии ведь не сказанно, как именно надо выкидывать.

но вообще-то, в небоскребах окна открываются?

[evgen2.livejournal.com]

Если речь про условия, то в условиях нет информации о наличии гравитации в месте расположения небоскрёба. Так же нет информации о что должна разбиваться бутылка. Теоретичски бутылка может разбиваться о стену небоскрёба и о другую бутылку.

[skolk.livejournal.com]

С этажей с номерами, кратными N по порядку, начиная со N-го, бросаем первую бутылку.
Когда она разбивается на этаже N*i, бросаем вторую, начиная с этажа N*(i-1)+1, с каждого этажа подряд.
Нам намекают выбрать N=sqrt(100)=10, но мне кажется, что N=2 было бы лучше. ;)

[kondybas.livejournal.com]

Да начать с первого и подниматься. Пока бутылка не бьется - ее можно "повторно использовать"(с)
Как разобьется - вторую с горя оприходовать.

[don-castelano.livejournal.com]

бить бутылки не обязательно полными.
обменять одну полную бутылку на int(log(100)) пустых.

бинарным поиском найти етаж.

вторую на радостях выпить

[udpn.livejournal.com]

Да не знает никто этой задачи на динамическое программирование. Это ж надо почитать какой-нить mccme, всё такое.

[http://users.livejournal.com/_slw/]

кстати, кроме таких неопределенностей (как кидать, открываются ли окна) -- а минимальное какое ищем?

минимальное в наихудшем случае? минимальное в среднем? в последнем случае -- какое распределение у принебоскребного покрытия?