Задача о двух шариках Опции

[klem4]

Дано:
- два абсолютно одинаковых шарика по размерам и свойствам
- дом в 100 этажей.
- 20 попыток

Бросаем шарик с этажа X - это минус одна попытка (при этом шарик может разбиться).
Одновременно можно сбросить только один шарик.

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

[Archon]

Archon, я так и не понял как ты сделал. Объясни, пожалуйста

Так же, как TarasBer.

Спойлер (Показать/Скрыть)

Сбрасываем первый шарик через некоторые промежутки пока не разобьется. Вторым шариком последовательно проверяем все этажи в последнем промежутке. Причем промежутки каждый раз надо выбирать не больше оставшегося числа попыток.

Например, если число попыток 20, то максимальный этаж, с которого можно сбросить шарик на первой попытке - 20. Тогда оставшихся 19 попыток как раз хватит на проверку этажей с 1 по 19. Если шарик на первой попытке не разбился, то далее его можно скинуть максимум с 39 этажа. Тогда оставшихся 18 попыток хватит на проверку этажей с 21 по 38. И так далее. Получается, что первый шарик сбрасывается с этажей 20, 39, 57, 74,...

В обобщенном виде номер этажа вычисляется по формуле:
F(i) = i*n - 1/2*i*(i-1), где i - номер попытки, а n - число попыток, которые мы намереваемся использовать.
При этом максимальный этаж, который мы можем проверить равен:
Fmax(n) = 1/2*n*(n+1)

Подставив высоту здания (100 этажей) в последнюю формулу, найдем минимальное число попыток.