Задача о шариках и небоскребе | Mozg.BY | Централизованное тестирование (ЦТ), задачи, тесты, олимпиады
Поступаем вместе!

Меню

Облако тегов:

Ссылки:





           

Задача о шариках и небоскребе

Эта задача предлагается для решения при собеседовании на позицию "программиста" в крупных компаниях. Для ее решения не нужно специальных знаний, хотя чтобы точно решить задачу в общем случае необходимы сведения из теории рядов.

Есть два стеклянных шарика: красный и синий. Вы находитесь в 100-этажном доме. Вам нужно определить номер этажа, начиная с которого шарик при падении разбиваются. То есть, нужно точно указать, что при падении с N-го этажа шарик не разбивается, а при падении с (N+1)-го уже разбивается.

За какое минимальное число шагов мы можем гарантированно определить этаж в самом худшем для нас случае? Какова стратегия быстрейшего поиска решения предложенной задачи?

Решить задачу для случая L-этажного здания и m шариков.

П.с.: Шаг - это один бросок одного шарика. Шарик начинает разбиваться с определённого этажа. Те кто знают, или думают что знают ответ, указывайте его в формате: {spoiler}ваш ответ{/spoiler], заменив { } на [ ].

Настройки просмотра комментариев

Выберите нужный метод показа комментариев и нажмите "Сохранить установки".

Скрытый текст:

Скрытый текст: выделите для просмотра
начинаем бросать шарики с этажей кратных 4(4, 8, 16...) и так пока не разобъем первый шарик. Пускай это произойдет на 4n этаже. Тогда бросаем второй шарик на 4n-2 этаже. Если разбивается тогда с 4n-3 шарики долетают целыми, иначе бросаем с 4n-1...
Для m шариков получаем формулу по этажам 2m. А потом делением полапам находим нужный этаж.

Не понял

А смысл синего и красного шарика? Какое значение имеет цвет или то что их 2?

Запутать

А это чтобы запутать посильнее.

И с "Матрицей" параллель провести...

кидалово)

Knight не согласен с приведенным тобой решением, объясняю почему:

Скрытый текст: выделите для просмотра
"Если разбивается с 4n-2 тогда с 4n-3 шарики долетают целыми" утверждение не корректно.... мы знаем точно что он целый упав с 4n-4, но про 4n-3 такое же сказать не можем...
например исходно шарик разбивается с 5го но целый с 4го, бросили с 4го - целый, бросили с 8го - разбился, бросаем с 6го - разбился, по приведенному решению получим N=5, а не 4.

да, ошибся

да, ошибся немного. Предложи свое решение, Lit!

борьба добра и зла

>Какова стратегия быстрейшего поиска решения предложенной задачи?
Как человек особо одаренный, вопроса не понял, уточните плз.

О шариках: очевидно*, реакция шариков не мгновенна, так что, падая с низких этажей, парашют раскрыть могут и не успеть. Шарик, не успевший раскрыть парашют – считается трупом. Этажи нумеруются сверху.

О цвете: мы все отлично понимаем, что важные дела не стоит пускать на самотек. Так что синяя таблетка - крашенная красная, и совершенно неважно, какие колеса глотал шарик.

Скрытый текст: выделите для просмотра
---m=1
простукивать надо все подряд, никаких фокусов
Пусть к - мин количество шагов, гарантирующих определение нужного этажа.
---m>=k
дихотомия** нам поможет - мы вполне проверим ею (2^k)-1 этаж
---m=j, шаг i
2 =0) пусть на шаге i-1 успешно спустили шарик с этажа Лi, j-1 шариком за k-i шагов можно простучать pLk-ij этажей. Тогда не выбрасывайте шарк с > pLk-ij+Li+1 этажа - примета плохая. Спустить его с этажа < pLk-ij+Li +1 точно не лучше чем с pLk-ij+Li +1 (если чего-то можно проверить j1 шариком за k1 шагов на L1 этаже, то на L2 меньше L1 тоже можно, а вот обратное не факт)
---Суммируем, суммируем и понимаем, что m шариками за k>m шагов можно проверить не более pLmk=(2^k)-sum (C***ik,i от 1 до k-m)-1 этаж. То есть, надо угадать такое минимальное k, при котором это будет больше L. Угадав, бросаем шарик на pLk-1j+1 , L1+pLk-1j+1, ... , этаже, пока он не разобьется, или пока нам не дадут воспользоваться честной дихотомией. Дальше пользуемся все той же старой доброй прокуренной логикой (если разбился, получаем задачу с pLk-ij этажами, k-i шагами и j-1 шариком).
---* все остальное тоже очевидно
---** вообще-то, бинарный поиск, если кому-то от этого легче
---*** кто же не знает силовика Ньютона, с его биномом.
А ответ на главный вопрос жизни, вселенной и всего такого - все же 42, а не 14.

Да, если обобщенную задачу предлагают решать устно, то это садисты. Не идите к ним работать.

Советую найти

Советую найти ответ для случая 100 этажей и 2 шариков прежде, чем писать всякие замутные решения. На самом деле у этой задачи достаточно простое решение.

Кстати, первый раз я увидел задачу 2 года назад на открытом личном первенстве России по программированию. Гена, откуда информация, что ее используют на собеседованиях?

Собеседование

Про то, что такая задача встречалась на собеседовании моему приятелю рассказал его друг, которому эту задачу задали. Разумеется, ее не надо было решать в общем случае прямо на собеседовании. Нанимателя интересовала, в первую очередь, логика человека, его уменее анализировать ситуацию. Задачу, кстати, он решил, но на работу все равно не попал - срезали на других формальных критериях...

Для 2х шариков -

Для 2х шариков - простое.

Скрытый текст: выделите для просмотра
Бросаем с 14, 27, 39,...,95,99 этажа, пока шарик не разобьется. Не разбился - бросаем с 100го. Разбился - бросаем второй с последнего этажа на котором не разбивался первый +1,+2,... пока не разобьется. Всего не более 14 шагов.

А для m - извращенное и приведено не полностью и не строго.)
Да, и прошу прощения за ошибки в индексах, в первом ответе.
pLmk -> pLkm+1
2=0) -> (L1=0)
Лi -> Li

а почему именно

а почему именно с 14, 27, 39,...,95,99 этажа?

просто не поняла

             
MOZG.by (C), 2007-2008 admin@mozg.by