Интересная головоломка

Первый шар мы можем бросать с любого этажа, но если он разобъётся, то придётся вторым последовательно проверить все непроверенные этажи ниже этого, начиная с нижнего из них.

Пусть число этажей N. Если выбросить первый шар с этажа P и он разобъётся, то вторым шаром придётся сделать в худшем случае P-1 проверок. Если же не разобъётся, то надо кидать с этажа 2 * P - 1. Минус один, потому что тогда, если на второй раз разобъётся, в худшем случае останется P - 2 проверок, а всего проверок столько же. Можно так сказать, что первой попыткой мы покроем P этажей, второй P-1 и т. д. Если на второй раз опять не разобъётся, то бросаем с этажа 3 * P - 3. Аналогично, потом 4 * P - 6, 5 * P - 10, 6 * P - 15  и т. д. Такие числа берутся оттого, что на каждой следующей попытке мы покрываем на один этаж меньше, а номер этажа получается равен сумме убывающей арифметической прогрессии (P, P-1, .....). Т. е. на каждом шаге S мы покрываем P - S + 1 этаж, а номер этажа будет (P + P - S + 1) * S / 2 = (2 * P - S + 1) * S / 2. Заканчивать придётся на броске S = P (или раньше), и этаж при этом должен быть, как минимум, N - 1 (если с него не разобьётся - ответ верхний N-ый, раз по условию точно известно, что с какого-то этажа разбивается, и раз не разбилось с предпоследнего, заведомо разобъётся с последнего). Если по условию неизвестно, разобъётся ли с верхнего этажа, то придётся подставить не N - 1, а N по вполне очевидным причинам.

Итого (2 * P - P + 1) * P / 2 >= N - 1
(P + 1) * P / 2 >= N - 1
P^2 + P - 2N + 2 >= 0

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

P >= (sqrt(8 * N - 7) - 1) / 2, где sqrt - квадратный корень.

Найденное значение округляем вверх до целого. Для N = 100 получается P >= 13,58, округляем вверх, получаем четырнадцать шагов.


Решение своё немного поправил, для N = 100 ответ от этого не изменился.