Помогите решить задачу по информатике.
В небоскребе n этажей. Известно, что если уронить стеклянный шарик с этажа номер p, и шарик разобъется, то если уронить шарик с этажа номер p+1, то он тоже разобъется. Также известно, что при броске с последнего этажа шарик всегда разбивается.
Вы хотите определить минимальный номер этажа, при падении с которого шарик разбивается. Для проведения экспериментов у вас есть два шарика. Вы можете разбить их все, но в результате вы должны абсолютно точно определить этот номер.
Определите, какого числа бросков достаточно, чтобы заведомо решить эту задачу.

Эта задача связана с известной проблемой оптимизации в информатике и называется задачей о двух шариках и этажах. Здесь важно минимизировать количество бросков в худшем случае, чтобы гарантированно определить этаж $p$, начиная с которого шарик разобьется.

Анализ задачи:

1. Если у нас есть только один шарик, мы можем определить этаж $p$, начиная с которого шарик разбивается, только перебирая этажи по одному, начиная с 1 и до $n$. В худшем случае потребуется $n$ бросков.

2. С двумя шариками можно действовать умнее. Используется подход, который сводит общее количество бросков в худшем случае к минимуму.

Оптимальная стратегия:

Оптимальная стратегия использует следующую логику:

• Первый шарик бросают таким образом, чтобы минимизировать общее число бросков в худшем случае. Если первый шарик разбивается, второй шарик используется для линейного поиска.
• Вместо проверки этажей равномерно (например, 10, 20, 30…), мы уменьшаем шаг при каждом броске, чтобы обеспечить оптимизацию.

Подход:

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

Для минимизации числа бросков в худшем случае сумма всех шагов должна быть равна $n$:

Эта сумма выражается формулой:

Отсюда можно найти минимальное $k$, решив это неравенство:

(здесь $\lceil x \rceil$ — это округление вверх).

Шаги алгоритма:

1. Найдите минимальное $k$, удовлетворяющее вышеуказанному неравенству.
2. Бросайте первый шарик с этажей $k, k + (k-1), k + (k-1) + (k-2), \dots$, уменьшая шаг на 1 после каждого броска.
3. Как только первый шарик разбивается на этаже $x$, используйте второй шарик, начиная с этажа $x - (шаг предыдущего броска) + 1$, проверяя этажи линейно вверх, пока не найдете точный этаж $p$.

Пример:

Предположим, что $n = 100$:

1. Решаем $\frac{k \cdot (k + 1)}{2} \geq 100$. Подставляя, находим $k = 14$ (так как $\frac{14 \cdot 15}{2} = 105 \geq 100$).
2. Бросаем первый шарик с этажей 14, 27 (14 + 13), 39 (27 + 12), …, пока он не разобьется.
3. Если шарик разбился, допустим, на 39-м этаже, проверяем этажи с 28 до 38 вторым шариком линейно.
4. Максимальное число бросков в этом случае составит 14.

Вывод:

Минимальное количество бросков, достаточное для заведомого определения этажа $p$, в худшем случае равно $k$, где $k = \lceil \frac{-1 + \sqrt{1 + 8n}}{2} \rceil$.