ry
Ни фига не понял задание... Обходим 100 этажей по-порядку и бросаем шарик. Начиная с какого-то, шарик должен разбиться. С какого именно - неизвестно, может быть, уже с первого. Тогда минимальное количество бросков - 1. И зачем второй шарик, непонятно? Чтобы каждый раз на низ не бегать?

PaulWist
SQRT(10**2) => 19 бросков.

Цитата:

Мы имеем в распоряжении два индикатора - два шарика. Как нас учили много лет, в науке два индикатора наиболее оптимально использовать, разделив их на индикатор грубой оценки, и точный индикатор участка, указанного грубым индикатором. Пока всем ясно?
Так вот первый шарик мы используем как грубый индикатор. С помощью него мы определяем тот интервал всего множества этажей, внутри которого находится искомая граница.
Этот интервал мы находим, кидая первый шарик с определенных этажей. Ну, например, как показал второй отвечающий, если мы кинули с десятого этажа, и шарик не разбился – значит, граница не в интервале 1-10 этаж, а вот если на двадцатом этаже шарик разбился - вот он, тот интервал, значит, наша граница находится на интервале 11-20
Пока все идентично тому, как решали приведенные мною участники? Ага ))) За одним малюсеньким исключением. Роль играет всего одно единственное слово, которого вы не найдете у меня, но которое по умолчанию присутствует в первом варианте и даже зачем-то специально оговорено во втором варианте. Это слово "одинаковых"
Родные вы мои! Любимые! Разве не учила вас жизнь, ВУЗ и даже школа, что самое оптимальное решение при индикации, это сделать все возможные варианты при индикации равной СЛОЖНОСТИ!
Возьмем вариант решения второго участника. Итак, если граница находится в первом интервале, сколько нам в самом неудачном случае бросков придется сделать? Правильно, десять - это если пограничный этаж десятый или девятый (не важно). А если граница в девятом интервале? Вот-вот, восемнадцать - девять бросков первым индикатором для определения интервала, еще девять бросков до девяносто девятого этажа, ну а последний, ладно уж, методом исключения )))
И что мы видим? Мы видим разницу в 8 этажей! Мы видим неодинаковые случаи, то есть неравномерное распределение количества работы в разных случаях! И естественно в таком неравномерном распределении самый неудачный случай окажется весьма большим! Единственный способ оптимизировать - распределить работу равномернее! Тогда, простите за каламбур, мы минимизируем максимум! Вот оно-то нам и надо!

Итак я доказала, что интервалы должны быть не равные. Но какие?
Ребенок догадается, что общее число попыток в интервале с номером N равно сумме номера этого интервала, то есть N и длины этого интервала, то есть числа этажей в этом интервале. Что надо сделать, чтобы эта сумма была одинаковой везде? Тоже элементарно, для сохранения суммы при увеличении одного слагаемого, должно столь же уменьшиться второе. То есть если первый интервал N=1 имеет длину k, то второй интервал будет иметь какую длину? Угадали, k-1. Сложно? Очень. Ну а интервал с номером N будет иметь длину k-N+1. Пока все понятно? Ясно откуда единица взялась?
Ну а теперь мы приходим к единственному участку решения, где требуется ну хоть какая-то простейшая база математики. Арифметическая прогрессия. Не трудно видеть, что здесь получается арифметическая прогрессия с разностью единица (новый член отличается на единицу) и начальным членом - тоже единица. (Почему начальный член единица? Потому что мы должны на всякий случай использовать нашу последовательность интервалов до конца, до самого последнего возможного интервала из одного этажа) Нам не известно одно - число интервалов и размер интервала (я сказала "одно" потому, что в последовательности такого вида данные параметры совпадают - k-тый интервал состоит из k этажей, надо найти только k)
Сумма всех наших интервалов - это есть сумма найденной арифметической прогрессии, правильно? Выводим простое свойство суммы арифметической прогрессии с шагом в единицу и первым членом = 1.

S = k(k+1)/2

А что нам известно про сумму в нашей задаче? Что она должна быть не меньше 99, но при этом быть минимальной. Логично? Вот и наша формула

k(k+1)/2 = 100

Решая это уравнение (находя его корень при положительном дискриминанте, если решать через дискриминант), и находя первое натуральное число, большее, чем корень, мы получаем ответ задачи. Этот ответ - 14 бросков.
За четырнадцать бросков мы смогли бы прочесать аж до 14*15/2 = 105 этажей (плюс один методом исключения)!
А теперь проверим решение. Имея в распоряжении два шарика, мы первый бросаем с четырнадцатого этажа. Если он бьется - то проходим вторым шаром от первого до 13-го. Первый разбившийся будет пограничным. Если не разобьется никто - пограничным признается 14-й. Если первый шарик не бьется при первом бросании, поднимаемся на 27-й этаж (14+13), ситуация повторяется, потом поднимаемся на 39-й (14+13+12), потом на 50-й, на 60-й, 69, 77, 84, 90, 95, 99.
Воть и все )))

Как видите, с такой формулой жить гораздо веселее. Во-первых, формулы - это вообще признак хорошего тона, это гораздо красивее, чем мы просто подбирали бы цифры и считали бы, получится с нею дойти до сотого этажа, или не получится, даже если по времени это меньше, чем на вывод формулы. Во-вторых, так гораздо универсальнее. Мы должны привыкать находить самые универсальные пути, которые можно применить при максимальном числе подобных задач. Так, например, теперь, если меня спросят про тысячеэтажный дом и с таким же условием, я не буду долго думать, а просто подставлю в готовую формулу вместо сотни - тысячу. Даже более того, усвоив простейшие принципы при решении такой задачи можно решить гораздо более сложную - при условии, что шара у нас три, четыре, p шаров; что было бы просто невероятно сложно, не дойди мы до описанных принципов. (кстати, кому интересно, может ради прикола вывести общую формулу для Х этажей и р шаров, теперь это очень легко)

Ну что, товарищи, я вам скажу на последок. Учиться, товарищи, учиться, и еще раз учиться! всем спасибо за внимание )))))))