Задачка о прочности шариков
 

Давненько задачек небыло.
Вот одна забавненькая. Легенда гласит, что несколько лет назад ее давали во время собеседования с потенциальными сотрудниками Microsoft.

Есть 100этажное здание с окнами на каждом этаже. У вас есть шарик, про который известно, что если его выбросить из окна на kом этаже или ниже - он упадет на землю и не разобъется. Если выбростить с k+1го или выше - упадет и разобъется.

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

Собственно задача: теперь у вас два шарика. Предложите способ точно определить число k за минимальное число бросков.

Математику:
Возможны обобщения: больше шариков, другая высота здания.

"Артиллерийская вилка": делим этажи на сектора по количеству шариков, начинаем бросать с нижнего этажа каждого сектора...

Это тест при приеме в Мелкософт? Да-а-а...

Не возьмут тебя в Microsoft :D

Ну если это два одинаковых шарика, и смысл с помощью их найти число "к" за минимальное кол-во бросков, то можно, как мне кажется, выкидывать каждый раз шарик с каждого второго этажа. Если на 20-ом не разбился, а разбился на 22-ом, то выкидываем второй шарик на 21-ом. Если разбился и там, число "к" = 20; если нет, то "к" = 21... :)

Appolon, Шарики одинаковые.
Но ответ ничем не лучше предыдущего. Понадобится (в худшем случае) 51 бросок.

"Есть способ лучше".

Мда..., это я поторопилси. :)

Блин, ну тогда с каждого десятого, а как разобъется, вторым шaриком искать этаж.

PS: И чем это я на работе занимаюсь?! Этажи считаю! Дожили. :lol:

Я бы каждый раз делила этажи на 2.
Сначала с 50-го кидаем, если разобьётся, то.. да... в худшем случае будет 50 попыток..
А если нет, то кидаем с 75-го (уже вполовину меньше попыток будет)....
И т.д.......

Я уже предлагал то же самое ("вилку"), только в варианте для произвольного количества шариков, так Анк только усмехается...

А давай кидать с nго этажа, потом с 2nго, потом с 3nго, пока не разобьется, опосля чего хватит еще n бросков 2-го шарика, чтобы уточнить этаж.

Наглый вопрос: а "усталость" и прочие микроповреждения шарика с каждым броском не накапливаются?

по-моему, 19 бросков хватит, может и меньше можно...

Ну так в принципе в мной предложенным способе и получится как раз 19 бросков, если предположить, что шарик кокнется с 100-го этажа. Значит мыслим одинакого. :)

Если k>100, то и за 100 бросков нипочем не найдешь.

А если так: проверяем этажи
14, 27(+13), 39(+12), 50(+11), 60(+10), 69, .... 99.
Итого хватит 14 попыток. Что характерно, если 100го этажа шарику мало, это определяется.

Возьмете меня в "мокрохвост"? Что дадут, то и раздолб... оптимизирую :) нафик

Сорри, прозевал твой пост, но я еще лучше придумал :)

Я знал, что решит только Kaktus.
Жаль, что не я беру в Microsoft.