ты точно знаешь что такое бинарный поиск?

А, нужно всегда нижний брать

хм...

подумай, а

пожалуйста

Это когда делим пополам же, нет?

а, т.е. если решать в лоб - то кидать с 1го и подыматься выше пока не начнет биться

это если в лоб, если бинарный поиск, то 50 -> разбилось -> осталось одно яйцо, подниматься с первого до удара

можно первое яйцо подымать на 10 этажей за раз

пока не разобьется, тогда вторым можно найти точный

тут алгоритм 10 -> 19 -> 28 -> 37 -> ... насколько помню

почему 9?

почему 9?

там 14, тогда, получается

а не 19

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

ну если прикидывать...

но я тупой и воспроизвести не смогу

если мы подымаемся по N этажей, то 100/N попыток и в среднем 100/N / 2 выйдет..

после чего N-1 попыток и в среднем /2

если мои прикидки верны, то при поднятии на 8-13 этажей, в среднем достаточно 9 попыток

что такое "поднятие на 8-13 этажей"?

ну

сперва мы определяем примерно этаж, подымаясь с первым яйцом на N этажей

если считать что нужный этаж может быть полностью и униформно случайным (от 1 до 100), то тогда нам понадобится от 1 до 100/N бросков, правильно?

да

т.е. мы можем усреднить и взять середину 100/N и поделить пополам - колво бросков в среднем для первого этапа

Вангую, хитрость задачи в том, что нужно использовать одновременно два яица

на втором этапе мы кидаем яйца от предыдущего этажа и подымаемся на 1 за раз, находя точный

так как интервал у нас составляет N, то в среднем на это уйдет N/2 попыток

Вангую, хитрость задачи в том, что нужно использовать одновременно два яица

в смысле брать автора задачи за них и выкрутить?

в среднем то да

а максимальное кол-во?

1 .. N-1

+ 100/N

в смысле брать автора задачи за них и выкрутить?

Не. И снизу вверх двигать, и сверху вниз

я в принципе оффбайван ошибки тут допускаю

сверху вниз можно, но очень недолго

итого имеем для выбранного интервала в N нам надо где-то около 50/N + (N-1)/2 попыток в среднем

К примеру, у нас всего 4 этажа. Бросаем со второго одно. Если разбилось, то первый этаж - варик. Если нет, то 3-4.

>>> f = lambda x:(50/x)+(x-1)//2 >>> print(*enumerate(map(f, range(1, 100)), 1), sep='\n') (1, 50) (2, 25) (3, 17) (4, 13) (5, 12) (6, 10) (7, 10) (8, 9) (9, 9) (10, 9) (11, 9) (12, 9) (13, 9) (14, 9) (15, 10) (16, 10) (17, 10) (18, 10) (19, 11) (20, 11)

т.е. интервал в 8-14 оптимален

Вангую, хитрость задачи в том, что нужно использовать одновременно два яица

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

Задача не решена, можно пиздовать за яйцами

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

Я не знаю каноничного решения этой задачи, но подобные темы в олимпиадных всплывают регулярно.

это не бинарный а логарифмический поиск выходит

т.е. интервал в 8-14 оптимален

блин, ну неправильная же формула(

блин, ну неправильная же формула(

я наверняка промазал в 100/N/2

или я не вдуплил, ты вычисляешь среднее?

но смотри - если ты подымаешься по 10 начиная с 10го - 10, 20, 30, 40, ... 100 это 10 попыток после того как бьется, надо проверять х1, х2, х3, х4... х9 этажи это 9 попыток если брать равномерное случайное распределение то это даст нам те самые 9-10 попыток что дает моя формула

среднее, да. исхожу из того что искомый этаж совершенно рандомный

чем длиннее интервал, тем меньше попыток в первой фазе, но больше во второй и наоборот. нам надо найти минимум их суммы - тут уже можно начать считать производные и прочую поебень

но простой перебор 50 вариантов и просмотр вручную тут достаточен

Если сбрасывать одновременно два яица: одно с первого, второе со второго, то количество попыток максимум 50.

в задаче не было ни слова про оптимизацию забега по лестницам здания

чем длиннее интервал, тем меньше попыток в первой фазе, но больше во второй и наоборот. нам надо найти минимум их суммы - тут уже можно начать считать производные и прочую поебень

это ты исходишь из варианта, что интервал при этом константен?

это ты исходишь из варианта, что интервал при этом константен?

а ты хочешь логарифм?

изврат

в задаче не было ни слова про оптимизацию забега по лестницам здания

Имхо, это будет наиболее точным решением.

Чюваки, задача не имеет решения.

Всего лишь два яйца.

Хлоп — ой, хлоп — ой. :(

два яйца - либо они у тебя есть, либо нет (с)

если бросаем по 13, то выходит что уже 13+, если 8, то 13+7

два яйца - либо они у тебя есть, либо нет (с)

Во, нормас.

это я про максимальное кол-во попыток, за которое ты точно определишь

в задаче вроде было нужно именно это

Максимальное — в районе 500 получается.

ERROR: S client not available

Потому что если человек долбоёб, то это на полную.

если бросаем по 13, то у нас в первой фазе 7 попыток, во второй 12 19/2 = 9 в среднем

если надо максимальное, тогда берем не среднее

100 этажей, двести, хоть 100500. Это для того, чтобы запутать. Минимальное количество этажей для решения кратное двойке.

ну и получается что порядка 19-20 попыток

> 7 попыток, во второй 12 да, я тебе могу предложит с меньшим кол-вом, если ты амортизируешь второе первым

то есть, например, если каждый раз поднимаешься на N - 1, N - 2 ... этажей

интервалы по 7-12 этажей дают нам 19 попыток макс

поднимаешься на 14 этаж, бросаешь, на 27 бросаешь, на 39 бросаешь ..

получится что 14

ага

и тут вопрос - а схуяли я взял что 14 это минимум?

но это надо подобрать

угу

пойду консультироваться с интернетом

вообще это напоминает мне логарифмический поиск фд в фдсете для селекта...

Да, берем квант в четыре этажа. Кидаем яицо со второго. Если разбилось, то первый, не разбилось, то кидаем с четвертого. Если разбилось, то третий. Если нет, то рекурсия

а почему не K/2+-1 этажей, где K - этаж, на котором разбивается яйцо?

ок, можно попробовать, K/3+1.

а, нет, нельзя.

Да, берем квант в четыре этажа. Кидаем яицо со второго. Если разбилось, то первый, не разбилось, то кидаем с четвертого. Если разбилось, то третий. Если нет, то рекурсия

По моему, это единственное решение

Причем, если кидать яица одновременно из четных этажей, то поиск ускорится.

Да, по идее, ускорение в два раза будет.

Кстати, помните задачку про ведмедя?

Медведь упал в яму-ловушку глубиной 19.617 метров. Время его падения составило 2 секунды. Какого цвета был медведь? А. Белый (полярный медведь) B. Бурый C. Чёрный D. Чёрно-коричневый (малайский медведь) E. Серый (гризли)

ыыы

Фуфло.

Кто знает, не пишите ответ, кто не знает, покумекайте без гугла

Канонiчная задача у Швейка Ярослава Гашека.

Канонiчная задача у Швейка Ярослава Гашека.

это интересно

это интересно

Ты не помнишь что ли?

это интересно

Ты на эту ответ знаешь?