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

[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.

[vak]

Первый правильный ответ, поздравляю!

[ubluzok.livejournal.com]

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

[vak]

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

[evgen2.livejournal.com]

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

[vak]

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

[getman.livejournal.com]

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

[vak]

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

[spamsink]

OT: Any news on the process?

[vak]

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

[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 яиц; я скопировал из задачек гугла для соискателей

[mr-tottor.livejournal.com]

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

[vak]

Да, так бутылок не напасёшься. :)

[cema.livejournal.com]

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

[vak]

Говорят, из Гугловского кандидатского минимума. :)

[chtovimenitebe.livejournal.com]

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

[vak]

Совершенно верно.

[maria-tuzhilina.livejournal.com]

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

[vak]

Я примерно такое же решение сразу выдал. Но понятно, что можно разумнее распорядиться второй бутылкой.

[golosptic.livejournal.com]

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

[vak]

Две.

[tnt23.livejournal.com]

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

[vak]

Получится 51 бросок. Можно раза в три поэкономнее.

[vak]

51 бросок получается - замучаешься вверх-вниз бегать. Можно раза в три сократить.

[skolk.livejournal.com]

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

[vak]

При N=2 имеем 51 бросок, при N=10 - 19 бросков. Можно еще лучше.

[kondybas.livejournal.com]

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

[vak]

Это ж сколько вверх-вниз бегать, да еще с грузом за пазухой. :)

[don-castelano.livejournal.com]

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

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

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

[vak]

Это инженерный подход. :)

[udpn.livejournal.com]

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

[vak]

Обычная олимпиадная задачка, класса для девятого наверное.

[dadv.livejournal.com]

N:=2.
Берем первую бутылку, кидаем со этажа N. Если разбилась, кидаем вторую с N-1 - если разбилась, ответ N-1, иначе N.

Если первая бутылка не разбилась с этажа N, то N:=N+2 и повторяем процесс, пока не пройдем все этажи.

За меньшее число попыток, не привлекая дополнительный материал типа алкашей и водопроводной воды, imho нельзя.

[vak]

Лучше можно, например если идти с шагом 10 а не 2. Но есть более оптимальное решение.

[ircicq.livejournal.com]

1. Шагаем начиная снизу с шагом 3 этажа:
3*i: 3, 6, 6, 12....
2. Как только разбилась, второй бутылкой уточняем:
3. бросаем из 3i-2: если разбилась, ответ 3i-2
4. бросаем из 3i-1: если разбилась, ответ 3i-1,
иначе ответ 3i

[vak]

Получается 35 бросков. Можно улучшить раза в два, даже больше.

[ircicq.livejournal.com]

Поправка: для минимизации максимального числа шагов нато шагать а первом этапе с шагом sqrt(число этажей), то есть с шагом 10

[vak]

19 бросков - неплохо, но не рекорд. :)

[denis-iv.livejournal.com]

1. в задаче не сказано, что нужно определить минимальный этаж, с которого разбивается. т.е. можно найти любой => бросаем с верхнего :)

2. если все же нужно найти минимальный, то первую бросаем с 50-го, если разбилась, то вторую по очереди с 1, 2, 3... пока не разобьется, а если первая не разбилась, то ее же бросаем с 75 и так далее...

вот тут насчет последовательности 50, 75... не уверен, возможно есть более оптимальные

[denis-iv.livejournal.com]

исправляюсь:
бросаем первую последовательно с 14, 27, 39... (уменьшаем интервал на 1).
бутылка бьется на i-m шаге - имеем интервал (14 - i) и i бросков уже сделано => максимум 14 бросков

[vak]

Да, оно самое.

[vak]

Круто! А для K бутылок? :)

[dadv.livejournal.com]

Всего 14 бросков.

Пусть f(x) - количество бросков в худшем случае для x-этажного дома.
Тогда:

f(1)  = 1
f(2)  = f(3) = 2
f(4)  = f(5) = f(6) = 3
f(7)  = ...  = f(10) = 4
f(11) = ...  = f(15) = 5
f(16) = ...  = f(21) = 6
f(22) = ...  = f(28) = 7
f(29) = ...  = f(36) = 8
f(37) = ...  = f(45) = 9
f(46) = ...  = f(55) = 10
f(56) = ...  = f(66) = 11
f(67) = ...  = f(78) = 12
f(79) = ...  = f(91) = 13
f(92) = ...  = f(105) = 14

[vak]

В общем да, такое себе аддитивное определение функции. :)