Бред

Ответить в тред Ответить в тред
Check this out!
Аноним 20/05/21 Чтв 10:47:37 2470343241
egg.jpg 19Кб, 1920x673
1920x673
>Дано 1000-этажное здание. Если яйцо сбросить с высоты N-го этажа (или с большей высоты), оно разобьется. Если его бросить с любого меньшего этажа, оно не разобьется. У вас есть четыре яйца. Найдите N за минимальное количество бросков.

Двачеры никогда не решат это
Аноним 20/05/21 Чтв 10:49:02 2470344092
Кстати это вступительная задача в 5-ый класс одной китайской школы...
Аноним 20/05/21 Чтв 10:50:02 2470344693
бамп
Аноним 20/05/21 Чтв 10:50:04 2470344724
>>247034324 (OP)
Ты идиот. Каким хуем я это должен узнать, чему равно n.
Яйца кидать идти?
Аноним 20/05/21 Чтв 10:50:51 2470345165
бамп
Аноним 20/05/21 Чтв 10:50:51 2470345176
чё дебил яйца с пол метра разобьются, так что я иду на 0
Аноним 20/05/21 Чтв 10:51:49 2470345787
>>247034324 (OP)
просто кидаешь с n-1 этажа, оно не разбивается. задача решена за 1 шаг
Аноним 20/05/21 Чтв 10:52:15 2470346058
Могу предположить, но погрешность будет в 32 этажа.
Аноним 20/05/21 Чтв 10:53:12 2470346679
>>247034605
Предположения запрещены.
Аноним 20/05/21 Чтв 10:54:36 24703475010
>>247034324 (OP)
вначале с 500
если не разбилось то с 750 если разбилось то с 250
короче делишь отрезки пополам
вот
Аноним 20/05/21 Чтв 10:55:14 24703479711
Рандомная хуйня. Берем худший случай - 124ый этаж.
Скидываем одно с 500го, разбивается.
Скидываем с 250го, та же хуйня.
Скидываем со 125го.
Остается одно яйцо, последовательно кидаем 123 раза, начиная с 1го.
Итого 126 бросков максимум.
Аноним 20/05/21 Чтв 10:58:58 24703504412
Кидаем с пятисотого этажа, если разбилось кидаем с 250-го, если снова разбилось кидаем с 125 этажа, если разбилось кидаем с 75 этажа, если разбилось кидаем с первого до 75-го поочередно, пока не разобьётся
Все случаи расписывать лень, но смысл решения понятен
Аноним 20/05/21 Чтв 10:59:31 24703507613
Аноним 20/05/21 Чтв 10:59:33 24703507814
>>247034797
Есть лучше. Берем худший случай 999 этаж.
Кидаем с 100го, с 200го, с 300го и т.д.
С 1000го разбивается.
Начинаем кидать с 900 до 999.
Итого 10 + 99 = 109 бросков.
Осталось придумать как выбрать промежутки вместо 100 с учетом 4ех яиц
Аноним 20/05/21 Чтв 11:00:21 24703512415
>>247035078
Никак
только пополам делить расстояния и потом докидывать
Аноним 20/05/21 Чтв 11:00:43 24703515216
>>247034324 (OP)

блять даже коню известно что бросив яйцо даже с первого этажа оно разобьется.
Аноним 20/05/21 Чтв 11:00:50 24703516717
>>247035044
У тебя уже разбилось 4е яйца и ты продолжаешь кидать?
Аноним 20/05/21 Чтв 11:01:33 24703521218
яйцо разобьется даже если упадет из рук на пол. О чем вы мамкины фантазеры наразу не готовящие в жизни себе яичницу?
Аноним 20/05/21 Чтв 11:01:38 24703521919
>>247035124
Я тебе уже привел пример со 100, который в любом раскладе оптимальнее твоего деления пополам
Аноним 20/05/21 Чтв 11:01:49 24703522820
Найти этаж на котором яйцо бьется? Да как нехуй на 1000 поднимусь и сброшу, изи.
Аноним 20/05/21 Чтв 11:02:53 24703528621
Аноним 20/05/21 Чтв 11:03:06 24703529722
>>247035078
Анон, ты гений.
Но у тебя после броска с 1000го еще 3 яйца, поэтому можно бросить с 950го, 975го и т.д.
Итого для 999го этажа выходит 15 или 16 бросков, в зависимости от выбора середины на нечетных этажах.
Аноним 20/05/21 Чтв 11:03:18 24703530823
>>247035228
Тебя не просят найти этаж на котором яйцо бьется.
>Найдите N
Аноним 20/05/21 Чтв 11:03:55 24703533824
>>247034324 (OP)
Пополам делить.
Если с N=500 разбивается, то берём N=250, если нет, то N=750 и т.д.
Аноним 20/05/21 Чтв 11:04:04 24703534925
Второй этаж. Зумеры блять.
Аноним 20/05/21 Чтв 11:04:19 24703536426
>>247035297
Я про это и писал.
>Осталось придумать как выбрать промежутки вместо 100 с учетом 4ех яиц
Там не факт что сразу надо кидать по 100, может есть оптимальнее вариант
Аноним 20/05/21 Чтв 11:06:39 24703549727
Аноним 20/05/21 Чтв 11:07:06 24703551728
Яйцо разбивается даже при падении из рук, долбоебы. Разобьется с любого этажа, задача некорректна.
Аноним 20/05/21 Чтв 11:09:20 24703563829
Аноним 20/05/21 Чтв 11:11:07 24703573830
>>247034324 (OP)
Я найду за 1 попытку. Кидаю с первого этажа, оно разбивается, ответ найден.
Аноним 20/05/21 Чтв 11:11:26 24703576231
Аноним 20/05/21 Чтв 11:11:58 24703579332
Там бинарным поиск для каждой половины нужно проверять, 4 яйца будет недостаточно. Нужно намного больше попыток.
\thread
Аноним 20/05/21 Чтв 11:12:19 24703581633
Аноним 20/05/21 Чтв 11:15:13 24703599734
>>247035638
Таким образом можно абстракцией назвать любой нелогичный бред.
Задача содержит в себе условие, что это именно яйцо и его разбиваемость при определенных условиях - тоже его неотъемлемый атрибут, а никакая не абстракция.
Аноним 20/05/21 Чтв 11:16:33 24703607335
>>247034324 (OP)
извлекаем корень 4 степени из 1000 и округляем, получаем 6
1000/6 = 166
166/6=28
28/6=5

Сперва кидаем на 166 этаже, потом на 332 и тд, пока не разобьется.
Если разбилось то этаж с 166 до 332
далее кидаем каждые 28 этажей например 194, 222, 250, 278. Пусть разбилась на 278
Далее кидаем каждые 5 этажей
255, 260, 265 - разбилось
далее на каждом этаже 261, 262 и тд. узнаем этаж

Худший случай 1 итерация 6, вторая 6, третья 6, четвертая 5 или ответ 23
реальный ответ может отличаться на +-5, так как не проверял
Аноним 20/05/21 Чтв 11:16:34 24703607636
>>247035638
>Челики, неспособные в абстракцию.
Кого ебут твои абстракции в реальном мире. Тебе ставят задачу - узнать с какого этажа разобъется яйцо. Правильный ответ - с первого.

Всё, иди нахуй, задача решена.
Аноним 20/05/21 Чтв 11:18:49 24703622837
>>247034324 (OP)
Пробую кинуть яйца с первых четырех этажей, если обсираюсь то просто отдаю аванс за решение и съебываю.
Аноним # OP 20/05/21 Чтв 11:20:09 24703631038
Аноним 20/05/21 Чтв 11:20:31 24703633139
>>247035638

Челик, делающий вид что не понимает что задача на понимание ее условий и ее вариациям лет больше чем шахматам.
Аноним 20/05/21 Чтв 11:21:48 24703641140
>>247034324 (OP)
Двачеры это никогда не решат, потому что это задача на оптимизацию из функционального анализа, 4 курс физмата, причём злоебучего.
Я тоже не решу, потому что от 4 курса я уже дальше многих местных обитателей.
Аноним 20/05/21 Чтв 11:25:53 24703666541
>>247036411
Ой не пизди, нет тут никакой высшей математики
миморешил

Кста, ответ - 13
Аноним 20/05/21 Чтв 11:31:33 24703699842
Алгоритм для 100-этажного здания уже давно придуман, максимальное количество шагов в нём равно 14. Значит, для 1000-этажного после этих 14 шагов нужно будет найти число внутри нужного десятка. Итого ещё 5 шагов, итого 19.
Аноним 20/05/21 Чтв 11:33:06 24703709143
>>247035219
Не в любом. Ты принимаешь, что худший случай - это 999 этаж, а на самом деле худший случай зависит от метода (и лучший тоже). Пусть у тебя яйцо бьётся на 751 этаже. Тогда метод с делением пополам даст тебе четыре броска (с 500 - не разбилось, с 750 - не разбилось, с 875 - разбилось, с 751 - разбилось), метод отсчитывать сотни будет заведомо хуже (не менее восьми бросков точно). Тут ещё очевидно кривое условие задачи - при фиксированном методе минимально возможное количество бросков будет зависеть от того, на каком этаже яйцо бьётся, собственно, если яйцо бьётся на первом этаже, то оптимальным методом будет "бросать на каждом, если не разбилось - подниматься на один", как ни странно - выяснить вообще первым броском. Так что правильная формулировка тут будет скорее "проводим множество экспериментов с разными яйцами, этажи n распределены равномерно, при каком методе среднее количество бросков будет минимально".
Аноним 20/05/21 Чтв 11:33:12 24703709844
>>247035997
Ну хочешь, это будут не 4 яйца, а 4 дилдака из неизвестного пластикоподобного вещества, которое может разлететься на куски от столкнлвения с землей.
Аноним 20/05/21 Чтв 11:35:02 24703720345
>>247034324 (OP)
Бросаю с первого этажа на траву.
/тред
Вы че ебанутые?
Аноним 20/05/21 Чтв 11:35:07 24703720946
Аноним 20/05/21 Чтв 11:37:02 24703732847
>>247036310
Скорее
>>при каком методе наихудшее количество бросков будет минимально".
Потому что в другом случае, твоё число в половине случаем не будет выполнять роль минимальности
Аноним 20/05/21 Чтв 11:40:55 24703756348
>>247034324 (OP)
Бросаю все яйца с одного этажа, а хули интересно как ебнет
Аноним 20/05/21 Чтв 11:43:17 24703771149
>>247034409
>Кстати это вступительная задача в 5-ый класс одной китайской школы...

Ну и? Ответ то будет?
Или это правда хуйня типа "оно разобъётся"?
Аноним 20/05/21 Чтв 11:44:14 24703778550
>>247037711
Нахуя тебе ответ на эту хуйню? Поступаешь в 5й класс китайской школы?
Аноним 20/05/21 Чтв 11:45:00 24703783351
>>247037711
Да был уже ответ, кидаем 3 попытки деля отрезки этажей попополам, 4м докидываем по одному этажу пока не найдем n , тут по другому и не решишь
Аноним 20/05/21 Чтв 11:45:01 24703783652
>>247037785
>Нахуя тебе ответ на эту хуйню?

Интересно
Аноним 20/05/21 Чтв 11:45:59 24703789553
Аноним 20/05/21 Чтв 11:46:59 24703795154
>>247034324 (OP)
Если это здание в России, я бы сам бросился оттуда, чтобы прекратить дальнейшие мучения в этом гулаге
Аноним 20/05/21 Чтв 11:47:02 24703795255
>>247037833
> n , тут по другому и не решишь

Не видел. Респехт.
Про многоразовость яйца недодумал
Аноним 20/05/21 Чтв 11:49:05 24703804756
>>247034324 (OP)
N=1, долбоёб. Ты яйцо последний раз когда в руках держал?
Оно даже с высоты пояса разобьётся, но 0,25 этажа нет, а 0 это уровень земли

С какими же кретинами я на одной борде сижу, хосспаде
Аноним 20/05/21 Чтв 11:49:59 24703811357
>>247037833

Но если у тебя N будет на верхних 62х этажах, то яиц не хватит
Аноним 20/05/21 Чтв 11:51:55 24703822358
>>247038047
>Допустим, у нас есть яйцо, которое разбивается, упав с высоты x≥n этажей
Так понятнее, долбоеб?
Аноним 20/05/21 Чтв 11:52:28 24703825959
>>247034324 (OP)
Здесь нужно 10 яиц, чтобы узнать этаж, только так можно перекрыть все варианты. Так что в данном случае бинарный поиск - идиотизм, лучше уже просто идти перебором с первого этажа вверх.

Понимаю, что двачеры могут работать только в макдональдсе, но вдруг, кто-то будет ходить по нормальным собесам. Есть похожий вариант задачи, только с другим вопросом. Вопрос может звучать, как:"Как за минимальное количество бросков узнать этаж на котором яйцо разобьется?"
Ответ на этот вопрос - как раз таки что за один бросок, когда яйцо разобьется с 1 этажа.

да это лайфхаки на двачах
Аноним 20/05/21 Чтв 11:52:46 24703827860
>>247037833
Доказательство оптимальности бы ещё было неплохо увидеть. И, кстати, формулировка задачи кривая, непонятно, что именно мы пытаемся сделать минимальным - наихудшее возможное или среднее ожидаемое? Кажется, что это разные вещи, ведущие к разным стратегиям.
Аноним 20/05/21 Чтв 11:52:58 24703828961
>>247034324 (OP)
Если яйцо не разбивается то его можно просто заново кидать с первого по н-ный этаж сколько влезет, все равно меньше попыток чем дрочиться по умному
Но всё равно один хуй задача хуевая и оп шалавий выблядок
Аноним 20/05/21 Чтв 11:54:43 24703839062
>>247034324 (OP)
К сожалению, я не могу ответить на этот вопрос в рамках договора о неразглашении информации.
Аноним 20/05/21 Чтв 11:54:44 24703839463
>>247038259
> лучше уже просто идти перебором с первого этажа вверх.

Доходишь до 4го этажа - яйца кончились. Твои действия?
Аноним 20/05/21 Чтв 11:55:43 24703846064
>>247038259
Даже с одним яйцом можно просто перебрать этажи по одному с первого по последний
Аноним 20/05/21 Чтв 11:56:24 24703850365
>>247038460
>сто перебрать этажи по одному с первого по последний

Да, только ровно наоборот - с последнего на первый
Аноним 20/05/21 Чтв 11:57:48 24703860266
>>247038394
Так они же не бьются до 4 этажа. Спускаешся, подбираешь, кидаешь дальше до 8 этажа
Аноним 20/05/21 Чтв 11:58:00 24703861567
>>247038394
яйца многоразовые, как я понимаю. Если яйцо не разбилось, то его можно использовать еще один раз.

Ну это все хуйня, тут привели выше более интересный способ, совмещения бинарного поиска для первых 3 яиц и перебора для 4 яйца.

>>247038460
Ну так можно, да.

>>247038503
Дружище, в таком случае, у тебя яйца закончатся раньше чем этажи. Ну хотя может ты свои оторвешь и кинешь, но на 1000 этажей все равно хуй наскребешь так.
Аноним 20/05/21 Чтв 11:58:10 24703862768
Аноним 20/05/21 Чтв 11:58:16 24703863669
Аноним 20/05/21 Чтв 11:58:22 24703865070
>>247038223
Во, с этого надо было начинать. Тогда бинарный поиск, но если идти с 1000 этажа то есть вероятность что на 125 последнему яйцу будет пизда
Аноним 20/05/21 Чтв 12:00:39 24703879971
xc3hne.jpg 23Кб, 600x450
600x450
>>247034324 (OP)
Нужно 10 яиц для 1024 этажного здания. Оп хуй, тред можно закрывать
Аноним 20/05/21 Чтв 12:00:43 24703880572
>>247036076
>Кого ебут твои абстракции в реальном мире.
Программистам, физикам-теоретикам, математикам. Но тебе не пригодится, можешь не переживать на этот счет. Тебе я думаю в жизни нихуя не пригодится, ты ведь долбоёб тупоголовый
Аноним 20/05/21 Чтв 12:04:22 24703901873
Аноним 20/05/21 Чтв 12:04:48 24703905274
>>247034324 (OP)
юзаюешь бинарный поиск 3-мя яйцами, пока все не разобьешь. Последним(если понадобиться) идешь последовательно вверх с самого низкого этажа, который получил на первом шаге.
Аноним 20/05/21 Чтв 12:05:34 24703910575
>>247035997
Ну точно дебил... Задача на математику и логику, а не на свойства яиц из реального мира
>>247036076
1000-этажные дома тоже в реальном мире существуют?
Аноним 20/05/21 Чтв 12:06:44 24703917476
>>247039052
>127 бросков
Серьезно блять?
Аноним 20/05/21 Чтв 12:06:51 24703918177
>>247038289
Там же ясно написано, минимальное количество бросков чтобы найти тот этаж на котором бьется. что ту т непонятного?
Аноним 20/05/21 Чтв 12:10:43 24703940578
>>247038278
Наихудшее возможное в классической постановке задачи.
Аноним 20/05/21 Чтв 12:11:03 24703943479
>>247038259
Двачую. В таких задачах как раз таки суть в вопросах которые задают. Самый лучший расклад, доебаться до вопроса на собеседовании, начать рассказывать какие варианты есть обойти и все такое прочее. Эйчары этого и хотят на самом деле, лол
Аноним 20/05/21 Чтв 12:12:27 24703952880
>>247034324 (OP)
Ты додик, бинарным поиском в 10 шагов находится только.
Условия задачи противоречивы и абсурдны сами по себе.
Аноним 20/05/21 Чтв 12:12:54 24703955681
>>247039405
Тут я вспомнил такие слова как "динамическое программирование". Два игрока: двачер и природа. Природа максимизирует броски, двачер минимизирует.
Аноним 20/05/21 Чтв 12:13:01 24703956682
>>247039174
на самом деле, да. Хуйня. Проще уже пойти так:

1. Кидаем с 500. Понимаем в какой половине наш этаж.
2. Потом идем по сотне. Например 600, 700 и т.д Получаем рейндж в 100 этажей.
3. Броском с середины отрезаем половину.

Получаем 50 этажей проверить последним яйцом + 3 начальных броска. Итого 53. Кто меньше?
Аноним 20/05/21 Чтв 12:17:57 24703986683
>>247035638
уебок, я ща тебе это яйцо об ебало разобью, ну и где твои учёные в говне моченые, помогли они тебе дебил ебанный?
Аноним 20/05/21 Чтв 12:26:59 24704043784
>>247039556
Динамическое программирование - это про другое, это когда ты находишь промежуточные решения, сохраняешь их, и дальше решаешь задачу, опираясь на ранее найденные решения
Аноним 20/05/21 Чтв 12:29:06 24704058585
>>247036076
>Кого ебут твои абстракции в реальном мире.
Все наше представление о мире - это абстракция.
У нас вычислительной силы мозга не хватит не абстрагироваться.
Аноним 20/05/21 Чтв 12:29:44 24704062486
>>247039528
Какая разница, за сколько шагов? Ограничения на количество шагов в задаче нет, его нужно просто оптимизировать.
Ты можешь даже одно яйцо кидать с 1, 2, 3, ... N этажа, пока оно не разобьется
Аноним 20/05/21 Чтв 12:29:59 24704064887
>>247039866
>уебок, я ща тебе это яйцо об ебало разобью, ну и где твои учёные в говне моченые, помогли они тебе дебил ебанный?
Но ты до сих пор мне ничего не разбил.
Выходит, что помогли.
Аноним 20/05/21 Чтв 12:30:07 24704065288
Аноним 20/05/21 Чтв 12:35:45 24704105189
>>247039105
Сам ты дебил. Подобные задачи проверяют логику, именно поэтому там яйцо. Замена яйца на дилдак меняет алгоритм решения.
У тебя, по-всей видимости, логика не работает.
Аноним 20/05/21 Чтв 12:38:02 24704119990
>>247034324 (OP)
Беру 4 яйца, засовываю их тебе в очко и скидываю тебя с 1000го этажа
Аноним 20/05/21 Чтв 12:38:28 24704122691
>>247041051
>Подобные задачи проверяют логику
Если бы это была задача для детсада, то да - логика про хрупкость яйца.
Но эта задача для математико-программистов, и тут уже логика про алгоритмы.
Аноним 20/05/21 Чтв 12:42:29 24704148792
>>247040624
>можешь даже одно яйцо кидать с 1, 2, 3, ... N этажа
>найдите N за минимальное количество бросков
>условия задачи противоречивы и абсурдны сами по себе
Всё понял?
Аноним 20/05/21 Чтв 12:43:59 24704158693
>>247039566
Бинарный поиск хорош, когда им можно идти до конца. Если его из-за недостатка яиц придется в какой-то момент прервать, то нужно думать в сторону какого-то другого - определяя нужную треть, четверть или что-то ещё.
Аноним 20/05/21 Чтв 12:47:00 24704182094
>>247034324 (OP)
1. Проверяем сначала граничные значения - кидаем с первого и последнего этажа. Если разбилось на первом - N = 1. Если не разбилось с 1000 - N невозможно определить с текущими условиями.
2. Если после проверки граничных значений нашли, что N между 1000 и 1 - начинаем проверять этажи с первого с шагом в 4. То бишь 1 этаж - 3 этаж - 6 этаж и так далее. На каком-то шаге яйцо разобьется - оставшимися двумя яицами выясняем точный этаж. Например, не разбилось на 120, но разбилось на 123 - кидаем с 121 и 122
Аноним 20/05/21 Чтв 12:47:56 24704188295
>>247041820
> с шагом в 4.
напиздел, с шагом в 3
Аноним 20/05/21 Чтв 12:48:08 24704189196
>>247041226
Если б это была задача на алгоритмы то вместо яйца была бы переменная, например "предмет" разбивается бла бла бла.
И главное в алгоритмах нет нелепых ограничений уровня "у нас было 4 яйца".
У меня в простейшей программке для датасаенс 500 миллионов циклов прокручивает при рассчётах и там оптимизация совсем иначе делается.
А это банально задачка на бинарный поиск с деревянными как и голова автора условиями.
Аноним 20/05/21 Чтв 12:49:03 24704194197
>>247041226
>Но эта задача для математико-программистов, и тут уже логика про алгоритмы.
Иди на хуй, в услових нет ничего про абстракции.
Аноним 20/05/21 Чтв 12:49:11 24704195498
>>247041051
> Сам ты дебил. Подобные задачи проверяют логику, именно поэтому там яйцо.
Так я и написал, что задача на логику, а ты зачем-то начал спорить. То, что изначальные условия задачи нереальны (сверхпрочное яйцо, 1000-этажный дом), не делает саму задачу, ход рассуждений и ее решение нелогичными.
> У тебя, по-всей видимости, логика не работает.
Ладно-ладно, ты победил
20/05/21 Чтв 12:50:18 24704203499
>>247039566
Ого зумеры изобрели бинарный поиск.
Только ты обосрался с подсчётом шагов не у тебя не 3 начальных шага а 2 + 4(600/700/800/900) = 6
Аноним 20/05/21 Чтв 12:51:25 247042118100
>>247041941
>в услових нет ничего про абстракции.
В условиях нет ничего про ответ, как же мы его найдем?
Аноним 20/05/21 Чтв 12:55:27 247042377101
>>247042118
Или на хуй, долбоёб. Задачи решают для получения ответа. Это самоочевидно.
Аноним 20/05/21 Чтв 13:02:25 247042801102
>>247034324 (OP)
Сначала бинарим делим тысячу на 2 -> 1 бросок
Потом проходим с шагом 100 -> 4 броска максимум
Находим нужную сотню. Проходим её с шагом 10 -> 10 бросков
Находим нужную десятку. Проходим её с шагом 1 -> 10 бросков

25 бросков ?
Аноним 20/05/21 Чтв 13:02:58 247042833103
>>247042377
Приведи пример задачи, в которой можно получить ответ не прибегая к абстракциям.
Аноним 20/05/21 Чтв 13:03:35 247042863104
>>247041954
>не делает саму задачу, ход рассуждений и ее решение нелогичными.
В рамках задачи все условия должны рассматриваться с точки зрения логики. Этаж может быть отличным от 1? Окей, тогда меням яйцо на пластмассовый дилдак. А пока в условиях яйцо, это неотъемлемая часть условий.
Аноним 20/05/21 Чтв 13:03:39 247042868105
>>247041051
Сукаблядь, бесят школьники и псевдоилитные гречневые гуманитарии. Дано, блядь, задание: найти оптимальный алгоритм. Нет, выёбываются: "Это яйцо, хы хы, оно с первого этажа разобьётся ёпта".
Аноним 20/05/21 Чтв 13:04:10 247042910106
>>247034324 (OP)
> Если его бросить с любого меньшего этажа, оно не разобьется
Нет, разобьётся. Какие же двачеры дегенераты, пиздец просто.
Аноним 20/05/21 Чтв 13:04:36 247042929107
>>247042833
Та же задача, с заменой яйца на стеклянный шарик.
Аноним 20/05/21 Чтв 13:05:44 247043010108
Аноним 20/05/21 Чтв 13:06:11 247043052109
>>247036998
14 - это два яйца в стоэтажном здании, а не четыре, так что вот так влоб не получится.
Аноним 20/05/21 Чтв 13:06:40 247043084110
ПОШЕЛ НАХУЙ, ПОДЗАЛУПИШЬ
Аноним 20/05/21 Чтв 13:10:16 247043303111
>>247037952
Уже было приведено решение лучше - кидаем первое яйцо с шагом 6^3, второе - с шагом 6^2, третье с шагом в 6. Но это все равно неоптимально.
Аноним 20/05/21 Чтв 13:10:31 247043316112
>>247042929
>Та же задача, с заменой яйца на стеклянный шарик.
И чем шарик принципиально отличается от яйца?
Мы считаем, что шарик не изменяет структуру после падения и не разобьётся, если его несколько раз сбросить с первого этажа.
Мы считаем, что все 4 шарика данные нам одинаковы, хотя в жизни это не возможно.
Мы считаем, что разбитие шарика происходит не зависимо от того, в какое место и каким боком он упал.
Это все абстракции. И их тут еще миллион, просто мы их принимаем как должное и даже не замечаем, ведь привыкли жить в них.
Аноним 20/05/21 Чтв 13:10:53 247043337113
>>247042868
Так надо и условия задачи ставить соответствующим образом.
Ответ для данной констретной задачи - 1.
Оптимальный алгоритм найден - яйцо разбивается, упав с 1 этажа, больше искать здесь нечего.
Нужен другой алгоритм - меняем предмет на другой.
Аноним 20/05/21 Чтв 13:11:51 247043402114
>>247034324 (OP)
после первого неудачного броска останется 3 яйца. с 3 яйцами можно будет определить один из 8 этажей гарантированно, т.е. первое яйцо нельзя бросать с шагом больше, чем 8 этажей. бросаем снизу вверх, это будет 125 бросков+еще 3 в худшем случае. всего 128 бросков в худшем случае
Аноним 20/05/21 Чтв 13:12:19 247043426115
>>247038805
Ты сам даун тупой блять, абстракция нужна чтобы решать РЕАЛЬНЫЕ ЗАДАЧИ. Без этого это нахуй не нужно, понимаешь?

К тебе приходит реальный заказчик и говорит "с какого этажа разобъется яйцо", ты ему отвечаешь "с первого". Ты дал ответ на вопрос, заказчик доволен, отдаёт тебе деньги и уходит.
Аноним 20/05/21 Чтв 13:13:32 247043499116
>>247043337
С чего ты взял, что яйцо разобьётся упав с первого этажа?
Куриное яйцо со стандартного дома на Земле разобьется.
Но тебе ничего не сказано ни про прочность яйца, ни про высоту этажей, ни про ускорение свободного падения, ни про вязкость воздуха.
Почему ты утверждаешь про первый этаж?
Установить этаж можно только опытным путем, что и просят сделать.
Аноним 20/05/21 Чтв 13:14:00 247043526117
>>247043426

Потом оказывается, что твоя программа-бросалка яиц делает бешеный перерасход, медленно работает и греет процессоры. А ещё её взломали хакеры и украли все яйца, потому что ты не умеешь в безопасность.

Заказчик уходит к тому, кто умеет решать задачи, а тебя потом ещё в суды таскают.
Аноним 20/05/21 Чтв 13:14:20 247043542118
>>247042868
>Дано, блядь, задание: найти оптимальный алгоритм

В задаче указано, найдите с какого этажа разобъется яйцо.

Ответ - с первого. Если ты составляешь ТЗ как мудак, то не бугурти потом.
Аноним 20/05/21 Чтв 13:14:22 247043544119
>>247042868
>Дано, блядь, задание: найти оптимальный алгоритм.
Окей.
Правильный ответ - шли запрос на ТКП. Подсчитаю затраты на решение задачи, как оплатишь аванс - начнем искать решение.
Аноним 20/05/21 Чтв 13:15:10 247043592120
>>247043316
Я буду считать иначе, т.к. шарик может и не разбиться, упав с 1 этажа.
Для решения задачи с шариком алгоритм будет другой.
В таком случае, сбрасываем каждый раз с центрального этажа из множества, в котором точно находится искомый этаж.
Однако, в условиях яйцо.
Аноним 20/05/21 Чтв 13:16:03 247043646121
>>247043426
>К тебе приходит реальный заказчик и говорит "с какого этажа разобъется яйцо", ты ему отвечаешь "с первого"
Кто-то решает и такие простые задачи.
Но ведь кто-то должен решать и более сложные?
Для них и сделана эта задача в качестве тренировки.
Аноним 20/05/21 Чтв 13:16:47 247043696122
>>247035044
Ты свои яйца будешь бросать, когда данные тебе 4 яйца закончились?
Аноним 20/05/21 Чтв 13:16:53 247043704123
>>247043499
>Установить этаж можно только опытным путем, что и просят сделать.

Можно узнать вес яйца и прочность скорлупы и посчитать.
Аноним 20/05/21 Чтв 13:17:26 247043726124
>>247035228
Какие же двачеры тупые, пиздос.
Аноним 20/05/21 Чтв 13:17:27 247043728125
>>247043592
Я тебе говорю про то, что ты хоть с шариком, хоть с яйцом прибегаешь к абстракциям в решении задачи. Без них невозможно решить ни одну задачу.
Аноним 20/05/21 Чтв 13:18:03 247043770126
>>247043592
>Однако, в условиях яйцо.
Не сказано, что за яйцо, может оно пластиковое.
Аноним 20/05/21 Чтв 13:18:58 247043825127
>>247042863
Окей, давай по-другому. Наверняка ты слышал про Задачу Коммивояжёра. Теперь давай представим, что коммивояжер перемещается между точками не на машине или общ.транспорте, а верхом на велоцерапторе. Тот факт, что велоцерапторы не существуют, как-то меняет логику решения задачи?

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

Я не знаю, может ты тут путаешь математическую логику и логику из картинок-загадок типа
> женщину нашли застреленной в голову, пистолет в руке, было ли это самоубийство или нет?
или
> Пионеры приехали на речку. Определите сколько пионеров приехало, когда они приехали, на чем они приехали, какая погода
Аноним 20/05/21 Чтв 13:19:04 247043830128
>>247035793
Попытался показать себя умным, но выставил себя затупком. Не можешь придумать алгоритм, для которого 4 яйца достаточно, дебил?
Аноним 20/05/21 Чтв 13:19:26 247043849129
>>247034324 (OP)
Ага ага, "список задач на собеседовании в гугл"
Аноним 20/05/21 Чтв 13:21:11 247043969130
>>247043728
Нет, я ещё прибегаю к намеренной критике долбоёба-составителя задачи. Хочешь выебнуться умом? Составляй задачу умно.
Я, как человек, изначально думающий хорошо про людей, пока они не доказали обратное, предполагаю, что автор конкретно такой задачи хотел наебать меня подвохом.
Поэтому для поиска того, о чём говоришь ты, я заменил яйцо на шарик. А рассказал про алгоритм в этом случае. Но у ОПа- яйцо.
Аноним 20/05/21 Чтв 13:23:00 247044071131
image.png 961Кб, 960x640
960x640
>>247043969
Почему ты думаешь, что яйцо обязательно разобьётся с первого этажа?
Аноним 20/05/21 Чтв 13:23:43 247044101132
Аноним 20/05/21 Чтв 13:24:14 247044127133
>>247043592
>Я буду считать иначе, т.к. шарик может и не разбиться, упав с 1 этажа.
Мы вам перезвоним
Аноним 20/05/21 Чтв 13:24:42 247044152134
image.png 1707Кб, 1500x1500
1500x1500
Аноним 20/05/21 Чтв 13:24:50 247044165135
>>247043825
Зачем ты поясняешь что-то человеку, троллящему тупостью?
Аноним 20/05/21 Чтв 13:25:27 247044202136
>>247044165
А он троллит занудностью, у них симбиоз, отьебись
20/05/21 Чтв 13:25:29 247044206137
Аноним 20/05/21 Чтв 13:25:55 247044232138
>>247034324 (OP)
Это загадка из собеседования в какую то тех компанию, эппл или майки, ещё книга есть со всеми этими вопросами
Аноним 20/05/21 Чтв 13:26:24 247044250139
>>247044127
Чел, это я "вам перезвоню". Если мудило приходит с кривым запросом, я отвечаю соответственно его запросу. Всё.
Аноним 20/05/21 Чтв 13:27:33 247044326140
>>247034324 (OP)
Бросаю с 0 этажа, яйцо не разбивается. Я подебил.
Аноним 20/05/21 Чтв 13:28:16 247044367141
image.png 1903Кб, 1200x800
1200x800
Отлично, с первым этапом вы справились, а теперь, продайте мне эти яйца.
Аноним 20/05/21 Чтв 13:29:28 247044455142
>>247043052
Ну а 19 - это два яйца на определение с точностью до десятка плюс два яйца на определение окончательной точности. Третьим яйцом можно устроить бинарный поиск, четвёртым - линейный.
Аноним 20/05/21 Чтв 13:29:29 247044457143
>>247044250
Хорошо-хорошо, мы вам перезвоним, вы нам перезвоните, но главное, покиньте здание
Аноним 20/05/21 Чтв 13:29:52 247044473144
>>247044206
Оно может быть и не куриным. Ок, тогда разобъётся максимум с 4 этажа. Найди такое, что не разобъётся? Не бывает? Ты соснул.
Каменное яйцо - это не яйцо. Пластиковое - тоже. Это макеты яйца. А по-умолчанию яйцо настоящее. Когда ты пишешь в договоре слово заказчик, ты тоже подразумеваешь, что на самом деле это не заказчик, а "актёр, исполняющий заказчика"? Вот так и в постановке задач следует следить за базаром.
Аноним 20/05/21 Чтв 13:31:05 247044554145
>>247044206
И где в задаче написано, что этажи стандартные, а не по 10 см?
Аноним 20/05/21 Чтв 13:32:02 247044614146
>>247044554
Вот за такие занудные вопросы тебе телки и не дают
Аноним 20/05/21 Чтв 13:32:24 247044640147
>>247044367
У вас же нет яиц.
А будут стальные, с 1000ого не разбиваются.
Аноним 20/05/21 Чтв 13:33:28 247044716148
Какие же тут сидят тупорылые животные, хуею просто. ЯЙЦО РАЗОБЬЁТСЯ НА ПЕРВОМ ЭТАЖЕ, МАМ, МАМ, Я РЕШИЛ ЗАДАЧУ С ПОДВОХОМ, А ТУПЫЕ ДВАЧЕРЫ ЧЁ-ТО ТАМ ВЫСЧИТЫВАЮТ СИДЯТ! КСТАТИ, О ДВАЧЕРАХ, НАДО ТРЕД СОЗДАТЬ. ПОМОГИТЕ ВКАТИТЬСЯ В АЙТИ, А ТО ЭТО ЩАС МОДНО, ЧЁ ТАМ ВООБЩЕ НАДО ТИПА ЗНАТЬ И УМЕТЬ?
Аноним 20/05/21 Чтв 13:33:53 247044749149
>>247044614
>Вот за такие занудные вопросы тебе телки и не дают

Вот за подобные ответы, тебя не возьмут ни на одну умственную работу:
>>247035517

Аноним 20/05/21 Чтв 13:34:59 247044833150
>>247044554
Здание, по-умолчанию, это постройка для жизнедеятельности человека. Расстояние между этажными перекрытиями не бывает 10 см. Ну а игрушечное здание- это не здание, а макет здания. Обоссан по фактам.
Аноним 20/05/21 Чтв 13:35:28 247044869151
image.png 68Кб, 320x200
320x200
>>247044473
Муравьиное. Как теперь жопой вилять будешь?
Аноним 20/05/21 Чтв 13:37:09 247044990152
>>247044749
Я С++-синьор. Это достаточно "умственная" работа?
Аноним 20/05/21 Чтв 13:37:46 247045038153
>>247044869
Сразу кидаю с тысячного и даю ответ N>1000
Аноним 20/05/21 Чтв 13:38:37 247045095154
пека мент бутылк.png 54Кб, 180x185
180x185
Так бля, тут же надо с 500 потом с 250, 125 и тд кидать, да? Ну или по сотке этажи отсчитывать а потом также десятки ебашить ну и единицы в конце? Пральна? Тред не читал.

мимо омоновец
Аноним 20/05/21 Чтв 13:39:53 247045177155
>>247044869
Хули ты мне фуфло подсовываешь такое? В условиях яйцо разбивается. Т.е. существует такая принципиальная возможность. Муравьиное не соответствует условиям задачи и превращает её в абсурд.
Аноним 20/05/21 Чтв 13:40:20 247045208156
>>247044990
C++-си boy ьор не понимает смыслов классических задач на алгоритмы, спешите видеть.
Аноним 20/05/21 Чтв 13:41:15 247045265157
>>247045177
>В условиях яйцо разбивается
>Муравьиное не соответствует условиям задачи и превращает её в абсурд.
А муравьиное не может разбиться?
Аноним 20/05/21 Чтв 13:41:29 247045274158
1xiILkSjBQGTQ3R[...].png 46Кб, 708x726
708x726
В АННАЛАХ ИНТЕРНЕТА НАЙДЕНА ТАБЛИЦА ДЛЯ ОБЩЕГО СЛУЧАЯ. ОТВЕТ - 13 ПОПЫТОК ДЛЯ ЛЮБОГО ЗДАНИЯ С ЭТАЖНОСТЬЮ ОТ 793 ДО 1092.

/thread
Аноним 20/05/21 Чтв 13:43:37 247045418159
>>247045208
Что, сидишь-обтекаешь, чмонька?
Аноним 20/05/21 Чтв 13:43:38 247045420160
>>247045274
С ЭТАЖНОСТЬЮ ОТ 1092 ДО 1470

Фикс. Пиздец я сонный и тупой.
Аноним 20/05/21 Чтв 13:43:39 247045421161
>>247045265
Нет, оно не разобъётся. Можешь проверить.
Аноним 20/05/21 Чтв 13:44:22 247045467162
>>247045420
Сука, нет, опятб обосрался, сначала же было верно. Ай, в пизду.
Аноним 20/05/21 Чтв 13:44:33 247045482163
>>247034324 (OP)
1) Кидаем со второго этажа если разбилось ответ = 1
2) Если не разбилось кидаем с последнего. Если не разбилось значит ответ =1000
3)Если разбилось сбрасываем с 501 этажа.
4)Далее разветвление в зависимости от того разбилось или нет делим верхнюю или нижнюю часть пока не останется одно яйцо.
5)Последним яйцом оставшийся участок проходим снизу пока не разобьётся.


Аноним 20/05/21 Чтв 13:44:44 247045498164
1519641872425.jpg 257Кб, 1200x900
1200x900
>>247034324 (OP)
разобъется с любого, ежу понятно же
только дебил или программист будет бросать яйца из окна и думать что не разобъётся

видишь, решил за ноль бросков твою задачу, ебло ослиное
Аноним 20/05/21 Чтв 13:46:03 247045579165
>>247045482
Потрясающий, гениально тупой алгоритм в 500+ ходов.
Аноним 20/05/21 Чтв 13:47:06 247045640166
>>247045482
Дружище, посчитай количество ходов в твоем худшем случае и количество ходов в худшем случае других алгоритмов из этого треда.
Посиди-подумай, почему ты такая тупая пидораха
Аноним 20/05/21 Чтв 13:47:57 247045691167
>>247044232
Классическая задача на собес - с двумя яйцами, и она нуу ощутимо проще, чем с четырьмя.
Аноним 20/05/21 Чтв 13:50:01 247045818168
>>247045691
Абсолютно то же самое. Тут даже комбинаторикой можно обойтись. Причём если с двумя яйцами и 100 этажами ответ 14, то здесь 13, т.е. ещё меньше.
Аноним 20/05/21 Чтв 13:52:00 247045935169
>>247034324 (OP)
ну так и одного яйца хватит если идти от меньшего к большему.
Оно ж не разбивается, значит сходил поднял и кидай снова этажиком выше, и так пока не разобьется.
В условии сказано, что у меня есть не 4 броска, а 4 яйца, ало.
Аноним 20/05/21 Чтв 13:52:33 247045972170
>>247044232
Да-да, её точно разбирали в книге gayle mcdowell'а "cracking the coding interview" для случая с большим количеством яиц.
Аноним 20/05/21 Чтв 13:53:23 247046021171
>>247034472
Алгоритм разработай, как бы ты искал N, если бы у тебя было здание и яйца.
Аноним 20/05/21 Чтв 13:54:27 247046102172
>>247045935
>Найдите N за минимальное количество бросков.
20/05/21 Чтв 13:55:03 247046146173
>>247034750
>вначале с 500
>если не разбилось то с 750 если разбилось то с 250
Пиздец, даун.
Аноним 20/05/21 Чтв 13:55:16 247046161174
>>247044455
Понятно что можно, но никто не гарантирует, что это оптимально - и, кажется, неоптимально. Собственно, даже внутри десятка двумя яйцами можно найти не за пять, а за четыре шага (то есть уже не 19, а 18), и совершенно не факт, что определять первыми двумя яйцами именно до десятка - оптимально, а почему не до 17, например?
Аноним 20/05/21 Чтв 13:55:46 247046198175
>>247035338
N=500, разбилось
N=250, разбилось
N=125, разбилось
N=62, разбилось

Яиц больше нет. Ответ - 2 этаж.
Аноним 20/05/21 Чтв 13:56:15 247046242176
>>247046146
та че он даун, это лучше, чем по сотке перебивать, если нас интересует минимальное количество шагов. Первым яйцом можно и рисковать
Аноним 20/05/21 Чтв 13:56:17 247046243177
>>247045935
Понятно, что можно тупо одно яичко ходить и кидать поочерёдно с 1, с 2, с 999 этажа. Вопрос в том, каков наиболее оптимальный алгоритм бросков. Ты в худшем случае кинешь яйцо 999 раз, то есть намудохаешься знатно, пока математик-кун будет стоять рядом и ржать со вспотевшей усталой собаки.
Аноним 20/05/21 Чтв 13:56:42 247046267178
>>247034409
>в 5-ый класс
Не верю, потому что для доказательства оптимальности алгоритма нужно проверить вариант с каждым этажом и для каждого алгоритма подсчитать максимум, минимум и среднее количество бросков.
Для полного решения задачи надо нахуярить алгоритм, который нагенерирует алгоритмы разбивки на отрезки, и проверит каждый из созданных алгоритмов.
Аноним 20/05/21 Чтв 13:58:46 247046387179
>>247045640
Ну всего два лишних броска которые зато могут сохранить от 3х до 4х яиц. Они либо решают сразу задачу либо позволяют использовать дальше двоичный поиск ведь если ими задача не решается то все 4 яйца остаются целыми..
Аноним 20/05/21 Чтв 13:59:48 247046450180
Аноним 20/05/21 Чтв 13:59:50 247046454181
>>247040624
>ограничения на количество шагов в задаче нет
>дано 4 яйца
20/05/21 Чтв 14:00:56 247046518182
>>247046242
Зачем кидать с 250, если с 500 оно не разбивается?
Аноним 20/05/21 Чтв 14:01:43 247046561183
>>247046387
Пижжю. С верхнего не надо кидать ты прав.
>>247045579
Ты тоже.
Аноним 20/05/21 Чтв 14:01:44 247046564184
>>247046242
Разумнее первое кинуть с 333 этажа и вообще работать с третями, а не с половинами. Тогда в самом худшем случае ты 4 яйцами определишь максимум 111 этажей, среди которых находится нужный. А твоим способом так можно определить максимум 125 этажей.
Аноним 20/05/21 Чтв 14:02:02 247046578185
Аноним 20/05/21 Чтв 14:02:44 247046620186
>>247034324 (OP)
Кидаю с первого. Если не разобьётся, то со второго, и так пока не найду максимальный этаж. Для поисков придется разбить всего одно яйцо.
Аноним 20/05/21 Чтв 14:03:10 247046641187
>>247046620
задача про кол-во попыток, а не кол-во яиц
Аноним 20/05/21 Чтв 14:04:50 247046735188
>>247034324 (OP)
>У вас есть четыре яйца
В оригинале их вообще два, машинным вычислением находится за 8 яиц вообще все варианты, задача не имеет смысла без конкретики.
Аноним 20/05/21 Чтв 14:05:00 247046746189
>>247034324 (OP)
шагаю в окно первого этажа, 2 яйца точно целы
Аноним 20/05/21 Чтв 14:06:00 247046790190
>>247046620
КИДАЕШЬ ЯЙЦО С ПЕРВОГО ЭТАЖА
@
РАЗБИВАЕТСЯ
Аноним 20/05/21 Чтв 14:06:20 247046808191
>>247046564
Бля, ошибся, там будет максимально 112 этажей, а не 111
самофикс
Аноним 20/05/21 Чтв 14:07:11 247046853192
>>247046564
Кидвешь с 333 этажа.
Не разбивается.
Аноним 20/05/21 Чтв 14:09:10 247046971193
Переформулирую задачу для тупых и хитрожопых.

Ебанутый арабский шейх отгрохал новенький 1000-этажный небоскрёб со скоростным лифтом. А ещё он намутил где-то яйца неизвестных науке динозавров, всего 4 штуки. Больше таких нигде нет. Но не забываем начало задачи, он ебанутый, поэтому он хочет эмпирическим путём установить, падение с какого этажа эти яйца способны выдержать. Для этого он вызвал тебя и поставил задачу: придумать способ узнать точный ответ, после чего за полчаса этот способ воплотить в жизнь (то есть поочередное кидание снизу вверх не подходит). Если не придумаешь, тебя ждёт казнь через побивание камнями. После того, как ты дашь ответ, тебя посадят в зиндан, а шейх проверит ответ, посоветовавшись с математиком-индусом. Если ответ неверный или ложный, тебя ждёт жесточайшая смерть с засовыванием колючей проволоки в анус.
Аноним 20/05/21 Чтв 14:09:19 247046980194
>>247045818
Мне не кажется , что прям то же самое. С двумя яйцами ты оптимиизируешь по сути только одну переменную - стартовое количество этажей по первому яйцу, дельта шага первого яйца задана однозначно тем, что у второго шаг может быть только единица. А тут тебе нужно найти стартовый шаг для трёх яиц и дельту шага для двух, это всё же разница.
Аноним 20/05/21 Чтв 14:09:39 247047004195
>>247046387
Ты ещё и в отказ пошёл. Сочувствую
Аноним 20/05/21 Чтв 14:09:47 247047011196
>>247034324 (OP)

В математическом "Форте Боярд" была такая задачка. Она вроде не тривиальная.
20/05/21 Чтв 14:11:44 247047154197
>>247046971
Шлю шейха нахуй, прилетает самолёт и бомбит нахуй этого грязного мюслю.
Аноним 20/05/21 Чтв 14:12:37 247047196198
image.png 43Кб, 200x200
200x200
>>247046790
КИДАЕШЬ ЯЙЦО СО ВТОРОГО ЭТАЖА
@
НЕ РАЗБИВАЕТСЯ
@
КИДАЕШЬ ЯЙЦО С ПЕРВОГО ЭТАЖА
@
РАЗБИВАЕТСЯ
@
ВДАЛЕКЕ ЗАВЫЛИ СИРЕНЫ
Аноним 20/05/21 Чтв 14:12:46 247047210199
>>247046564
Если делать так (каждым яйцом искать равные доли), то анон в начале треда правильно заметил, что тогда уж брать корень четвертой степени из 1000 и делать третьим яйцом шаг 6, вторым - 36, первым - 216. Но это неоптимально решение.
Аноним 20/05/21 Чтв 14:13:45 247047270200
>>247034324 (OP)
Начать кидать с первого этажа, оно не разбивается, берём его(так как оно целое осталось) и поднимаемся на 2 этаж и так пока не разобьётся итого нашли, потратив всего 1 яйцо
Аноним 20/05/21 Чтв 14:13:53 247047278201
>>247046620
Анончик, да ты гений, разъебал всех мамкиных карзиночек выше
Аноним 20/05/21 Чтв 14:15:59 247047408202
>>247034324 (OP)
> У вас есть четыре яйца.
Бросаем с 100 этажа начиная повышать на 100 каждый раз.Если разбилось на 500м например то идем на 400й и начинаем 3-м яйцом проверять с 410го повышая на 10 этажей, если разбилось например на 450-м, то идем на 441 и с него 3-е яйцо сбрасываем повышая на 1 этаж каждый раз.
4-е яйцо можно съесть, ибо я хуй знает как задачу оптимизировать вокруг него.
Аноним 20/05/21 Чтв 14:16:43 247047458203
500
250
22
22+21
22+21+20..

24 броска
Аноним 20/05/21 Чтв 14:17:26 247047504204
Аноним 20/05/21 Чтв 14:17:38 247047513205
1621509458431.jpg 216Кб, 1440x1692
1440x1692
>>247034324 (OP)
Задача для долбоебов.

Задача найти место где оно начнёт разбиваться ? Ок

Кидаем с первого этажа до момента когда оно разобьётся. Потратим одно яйцо. Профит
Аноним 20/05/21 Чтв 14:18:13 247047550206
>>247047408
Ну, ты можешь лишнее яйцо кинуть в середину, срезав таким образом сразу половину неверных ответов. Но решение все равно тупое.
Аноним 20/05/21 Чтв 14:20:06 247047652207
>>247047513
У тебя что, задача сэкономить яйца, нищук ты потомственный? Пиздец.
Аноним 20/05/21 Чтв 14:21:22 247047719208
>>247047652
Тут где-то писали что есть 4 яйца. Вот я про этот случай говорю
Аноним 20/05/21 Чтв 14:22:35 247047803209
Аноним 20/05/21 Чтв 14:24:12 247047904210
Говно вы тут пишете. А если яйцо не разбилось, но треснуло?
Нужно искать только в том интервале, вверху которого оно точно разбилось и внизу которого точно треснуло.
20/05/21 Чтв 14:26:20 247048023211
Аноним 20/05/21 Чтв 14:32:58 247048387212
НАХУЯ?
Аноним 20/05/21 Чтв 14:33:05 247048392213
>>247034324 (OP)
Кидаю на 500м этаже, не разбивается- поднимаю на 250 этажей, разбивается- опускаю на 250 этажей.
Уже на новом этаже по той же схеме сдвигаю еще на 125 этажей.
Потом еще на 63, точнее не могу, еще 5 бросков и я установлю точную границу этажа, где разобьется или нет.
Аноним 20/05/21 Чтв 14:37:08 247048611214
>>247046564
Если делить пополам то четырьмя яйцами ты найдешь диапазон 62,5 а не 125.
Аноним 20/05/21 Чтв 14:39:12 247048730215
Аноним 20/05/21 Чтв 14:42:58 247048972216
Аноним 20/05/21 Чтв 14:43:42 247049013217
>>247034324 (OP)
Девять бросков, ровно девять бросков мне понадобится чтобы вычислить N, не меньше, не больше.
Аноним 20/05/21 Чтв 14:46:38 247049176218
>>247034324 (OP)
Лол, я понял, НАСКОЛЬКО задача становится проще, если ее перевернуть наоборот. Не "задано число яиц и этажей, определить число попыток", а "задано число яиц и попыток, определить максимальный этаж", после этого решается примерно на изи.
Аноним 20/05/21 Чтв 14:49:08 247049318219
>>247049176
>задано число яиц и попыток
Даю тебе четыре яйца и две попытки
Аноним 20/05/21 Чтв 15:04:44 247050307220
>>247049176
В общей задаче для N и M я нихуа не понял, что называется попыткой. В той, где 100 этажей и 2 яйца, что считается попытками?
Аноним 20/05/21 Чтв 15:06:13 247050409221
>>247050307
Бросок яйца (неважно, разбилось оно или нет), собственно то, что нам нужно найти.
Аноним 20/05/21 Чтв 15:06:59 247050461222
Аноним 20/05/21 Чтв 15:09:35 247050650223
>>247049318
Три этажа максимум, в чем проблема? Первый бросок со второго этажа, если разбилось - то второй бросок с первого. Если не разбилось - то второй бросок с третьего. Два яйца при любом раскладе лишние, бывает.
Аноним 20/05/21 Чтв 15:12:27 247050837224
>>247050650
>то второй бросок с третьего
Тоже разбилось
Аноним 20/05/21 Чтв 15:15:25 247051010225
>>247050837
Значит ответ -первый этаж
Аноним 20/05/21 Чтв 15:23:24 247051505226
>>247034324 (OP)

Кидаем на 50. Если не разбилось - идем выше. Разбилось - ниже. Кидаем на 25 или 75. Повторяем процедуру, разделяя промежуток на две части. Когда остается одно яйцо, а остальные разобьются - берем нижний предел промежутка и начинаем бросать каждый раз поднимая на 1. На каком разобьется - тот этаж - это искомое N.
Аноним 20/05/21 Чтв 15:25:05 247051602227
>>247034324 (OP)
С 1000 этажа. В чем проблема? А так каждые 250 этажей кидать
Аноним 20/05/21 Чтв 15:25:22 247051622228
>>247034324 (OP)
Ты еблан? Я только что скинул яйцо с первого этажа, оно разбилось. Долбаёб, блядь. Задачу свою в жопу себе засунь, мудак
Аноним 20/05/21 Чтв 15:27:41 247051741229
>>247051010
А нахуя для этого яйца бить?
Аноним 20/05/21 Чтв 15:27:41 247051743230
>>247034324 (OP)
Ну сначала кидаешь с середины здания, то есть с 500 этажа.
Если разбилось, то с середины той половины, что ниже этажа, с которого кидал.
Если не разбилось, то с середины верхней половины.
Так повторяешь пока не разобьешь все яйца кроме одного, им прокидываешь по одному этажу снизу вверх оставшийся интервал.
Аноним 20/05/21 Чтв 15:29:08 247051828231
Худший сценарий:
1. Идем с шагом 200 (4 попытки, бьем одно яйцо)
2. Идем с шагом 50 (3 попытки, бьем одно яйцо)
3. Идем с шагом 16 (2 попытки, бьем одно яйцо)
4. Оставшиеся 15 этажей последовательно проверяем последним яйцом.

Итого 23

Где я проебался?
Аноним 20/05/21 Чтв 15:33:12 247052122232
Аноним 20/05/21 Чтв 15:33:31 247052136233
Первые 3 яйца для нахождения нижней планки, считаем что она стремится к 0.
Кидаем первое яйцо с 1 этажа, если не разбилось то со 2, 4, 8 и так далее, пока не разобьётся на этаже Z.
Соответственно нашли старший бит числа N, то есть знаем, что N лежит между Z/2 и Z.
Затем выбираем половину в этом диапазоне, Z/2+Z/4.
Если не разбилось, снова поднимаем этаж на вдвое меньший. Повторяем, пока второе яйцо не разобьётся.
Этим уточнили интервал – он между этажом в предыдущей попытке и текущей.
Аналогично третьим яйцом ещё раз сокращаем доступный предыдущий диапазон.
Четвёртым яйцом с нижней границы полученного диапазона проверяем каждый этаж, поднимаясь выше.
Аноним 20/05/21 Чтв 15:34:40 247052211234
>>247052122
Это понятно, по сути будет ответ?
Аноним 20/05/21 Чтв 15:35:53 247052296235
>>247052211
Да. По сути ты пидор дырявый
Аноним 20/05/21 Чтв 15:36:10 247052318236
>>247050837
Что значит "тоже"? Если оно разбилось на втором, то вторую попытку пускаем на проверку первого этажа. Если на втором НЕ разбилось - то тогда кидаем с третьего, если на третьем разбилось - то мы выяснили, что бьётся начиная с третьего и выше, не разбилось - хз, бьётся где-то высоко, не можем сказать (собственно, не совсем корректно сформулировал обратную задачу, да - при заданном числе яиц и попыток назвать максимальное n такое, что если яйцо бьётся при броске с n-ного этажа и выше, то мы можем экспериментально установить это n - в такой формулировке n=3, если яйцо бьётся при броске с минимум первого, второго или третьего, то мы это экспериментально проверим, если при броске минимум с четвертого или больше - то нет).
Аноним 20/05/21 Чтв 15:38:29 247052476237
>>247052136
Ну и как вам мой нереальный рисунок карандашом?
Аноним 20/05/21 Чтв 16:08:09 247054553238
Покормлю.
Представим здание как отрезок длиной N на котором могут находится натуральные числа. Делим его на 4 равные части (нужно провести три границы для этого). С каждой начерченной границы выкидываются по одному яйцу. Далее выбирается новый отрезок между границами где одно яйцо разбилось (высокая грань) и где не разбилось. Собираем оставшиеся яйца и делим выбранный отрезок на k равных частей (k - количество оставшихся яиц) и повторяем тот же алгоритм. Если k равно 1, то идем от нижней грани до высшей с шагом 1 (тут уж ничего не поделаешь). Надеюсь понятно объяснил.
Аноним 20/05/21 Чтв 16:09:06 247054630239
Аноним 20/05/21 Чтв 16:10:20 247054731240
20/05/21 Чтв 16:10:53 247054771241
>>247035152
>>247035286
>>247035212
>>247035349
>>247035497
>>247035517
>>247035997
Что вы за ебланы, кто блядь вам сказал что это куриное яйцо, это блядь нахуй может быть яйцо ебаптозавтра с планеты жопа нахуй, и вы не ебете когда оно разобьётся овощебазы ебаные съебите с моих двачей
Аноним 20/05/21 Чтв 16:12:01 247054859242
>>247051828
Вот тебе алгоритм неоптимальный, но лучше чем твой. Кидаем яйцо со 140го, потом с (140+130)=270го, потом с (270+120)=390го и так далее вплоть до (140+130+120+110+100+90+80+60+50+40)=990 этажа и последний бросок на 1000), пока яйцо не разобьётся. Назовем тот этаж, на котором оно последний раз не разбилось, n1 (если оно разбилось на 140м, то n1=0). После этого кидаем второе яйцо с этажа (n1+10), потом (n1+20) и так далее до следующего этажа, который мы проверили в первый раз. Если первое яйцо разбилось на 140м, вторым яйцом мы сделаем в худшем случае 13 бросков - итого 14 вместе с первым. Если первое яйцо разбилось на 270, то вторым мы сделаем максимум 12 бросков - итого опять 14 вместе с первым. И так далее. Таким образом суммарно двумя яйцами мы сделали максимум 14 бросков и теперь мы знаем число n2 такое, что на этаже n2 яйцо ещё не бьётся, а на этаже n2+10 - бьётся. Теперь третье яйцо кидаем с n2+4, n2+7, n2+9, соответственно, последним яйцом проверяем оставшиеся этажи, на последние два яйца уйдут максимум 4 броска, итого мы нашли этаж за 18 бросков, а не за 23, как у тебя.
Аноним 20/05/21 Чтв 16:21:31 247055555243
>>247054731
Тогда дели на грани этаж 100, 300, 600, (ну и последний 1000). Дальше найдя нужный отрезок дели его оставшимися яйцами по похожим соотношениям.
Аноним 20/05/21 Чтв 16:27:32 247056029244
>>247055555
Весь подход неправильный, на самом деле. Равные соотношения не дадут оптимального алгоритма, какими бы они ни были.
Аноним 20/05/21 Чтв 16:34:07 247056535245
>>247056029
Эм. Где ты тут видишь равные соотношения? Говорю первое выкидывается с 100. Если не разбилось - с 300, если и не разбилось дальше - то с 600. А если на каком-то разбилось то берем отрезок между двумя гранями и делим по такому же принципу. Если интересно почему принцип таков, то напишу вот такое уравнение:
x + 2x +3x +4x = 1000
10x=1000
x=100

Первая грань 100, вторая на 2x больше (300), третья на 3x больше (600).
Аноним 20/05/21 Чтв 16:47:38 247057517246
>>247034324 (OP)
Кидаю с 1 этажа, оно разбивается, значит N = 0. Все.
Аноним 20/05/21 Чтв 16:53:56 247058001247
>>247054859
Я думаю можно за 16 сделать.
Аноним 20/05/21 Чтв 16:59:25 247058386248
>>2470343
ОП. Ответ будет?
Аноним 20/05/21 Чтв 17:00:14 247058434249
Asd
Аноним 20/05/21 Чтв 17:03:19 247058621250
>>247054859
Если яйцо с 999 только начинает разбиваться, то твоя стратегия идёт по пизде
Аноним 20/05/21 Чтв 17:04:12 247058672251
>>247034324 (OP)
Пизда двачеры тупые. Вам не сказано какая высота дома, соответственно не факт что с первого этажа если кинуть - оно разобьется.
Ответ: кидать по очереди с первого этажа. Разобьется с этажа N-1.

/threat
Аноним 20/05/21 Чтв 17:05:36 247058753252
Задача хуйня для лошков. Поехали с задачей посерьёзнее.
Дано m-этажное здание. Если яйцо сбросить с высоты N-го этажа (или с большей высоты), оно разобьется. Если его бросить с любого меньшего этажа, оно не разобьется. У вас есть n яиц. n < m. Найдите N за минимальное количество бросков.
Аноним 20/05/21 Чтв 17:05:59 247058778253
>>247058001
За 13 можно сделать. Причем посчитать это в целом проще, чем расписать сам алгоритм, что интересно.
Аноним 20/05/21 Чтв 17:05:59 247058779254
>>247034324 (OP)
Какой уебан придумывает эти ебанутые аналогии с яйцами и небоскребами?
НАЙДИ Х В ДИАПАЗОНЕ ОТ 1 ДО 1000, БЛЯДЬ
Какие этажи сука, наркоман
Аноним 20/05/21 Чтв 17:06:28 247058805255
Аноним 20/05/21 Чтв 17:13:42 247059232256
>>247058778
Там же делишь на отрезки которые растут по размеру? По моему это называется логарифмическая шкала.
Аноним 20/05/21 Чтв 17:15:32 247059343257
126 бросков
Кидаем с 500, разбиваем, кидаем с 250, разбиваем, кидаем со 125, разбиваем. Оставшимся ейцлм проходим с 1 до 123, этого достаточно, и того 123+3=126
Если на каком-то из пунктов яйцо не разбивается, то будет меньше бросков, чем в этом случае. Это худший случай, а потому исчерпывающий. Все формально доказывать мне лень.
Алгоритм: начинаем с 500, кидаем, далее делим пополам верхнюю пятихатку, если не разбилось и кидаем с 750, а если на 500 разбилось, то кидаем с 250. Так делим на два наш промежуток и кидаем, пока не останется одно яйцо. Этим яйцом проходим с самого высокого этажа где не разбилось до самого низкого, где разбилось. Это точно не больше 123
Аноним 20/05/21 Чтв 17:17:18 247059438258
>>247058753
Двачую. ) Правда это уже жестко сложность возрастает.
Аноним 20/05/21 Чтв 17:19:45 247059592259
>>247059343
> Кидаем с 500, разбиваем
А если не разбиваем?
Аноним 20/05/21 Чтв 17:20:23 247059644260
>>247059343
Мой алгоритм работает. Выше у быдла получается больше бросков при крайних значениях типа н 999 или н 1
Принимаю претензии и критику в отношение моего алгоритма.
Аноним 20/05/21 Чтв 17:21:02 247059683261
>>247058753
> m-этажное здание.
Это что то из техпаспорта путинских новостроек?
Аноним 20/05/21 Чтв 17:21:05 247059688262
>>247058621
У нас в здании всего 1000 этажей, то есть тебя смущают варианты 999 и 1000 только. В любом из них я делаю 11 бросков первым яйцом, узнаю, что на 990 оно не бьётся, а на 1000 уже бьётся, вторым яйцом делаю ноль бросков (мне и так известна десятка этажей), третье яйцо кидаю на 994, 997 и 999 (14 бросков). Если яйцо не разбилось на 999, то ответ - 1000, этот этаж я проверил первым яйцом. Если яйцо разбилось на 999, то я бросаю четвертое яйцо с 998 и по результатам этого броска говорю 998 или 999 (итого 15 бросков).
Аноним 20/05/21 Чтв 17:22:15 247059770263
>>247059592
Это худший случай, прочитай весь пост. Если не разбиваем, то кидаем с 750, далее либо с 625 либо с 875 и т.д, пока не останется одно яйцо, которым мы проходим по всему диапазону от максимального неразбившегося до минимального разбившегося.
Я бля в посте том все это расписал
Аноним 20/05/21 Чтв 17:24:32 247059916264
Аноним 20/05/21 Чтв 17:28:25 247060208265
Аноним 20/05/21 Чтв 17:33:30 247060522266
>>247054859
Неплохо. Мимо автор говна с 126 бросками
У тебя даж 17 получится, ибо когда знаем а и а+10, между которыми искать, мы за 3 броска найдём среди 9 оставшихся нашу хуйню. Один в а+5, воторой либо в а+2 либо в а+7, ну и третий понятно куда.
Аноним 20/05/21 Чтв 17:36:51 247060740267
>>247035793
Типа больше способов нет?
Я то тоже из алгоритмов поиска знаю только бинарный, но не стал высирать свое мнение
Аноним 20/05/21 Чтв 17:37:21 247060769268
>>247034797
> Остается одно яйцо, последовательно кидаем 123 раза, начиная с 1го.
Нахуя? Лучше снова делать по половине. Т.е. кинуть с 62 этажа, потом с 93 и тд.
Аноним 20/05/21 Чтв 17:38:56 247060872269
>>247059644
Даже банальный алгоритм уровня "кинули сначала на каждом сотом, потом на каждом десятом, потом на каждом первом" даст не более 30 бросков в худшем случае, против твоих в худшем случае 123. И как раз для 999 этажа бросков у тебя будет овердохера.
Аноним 20/05/21 Чтв 17:39:11 247060885270
>>247034324 (OP)
> У вас есть четыре яйца
Охуел? Бинарному поиску на таком диапазоне больше итераций потребуется
Аноним 20/05/21 Чтв 17:47:06 247061432271
Я решил! Берём 4 яйца и ебашим вкуснейшую яишинку, а потом прыгаем с 1000го этажа.
Аноним 20/05/21 Чтв 17:49:58 247061653272
мясо просо коле[...].webm 1951Кб, 640x480, 00:00:27
640x480
>>247034324 (OP)
Высиживаю их пока не вылупляться, вскармливаю их грудью и спермой пока не оперяться и научаться летать, и спокойно отпускаю
Аноним 20/05/21 Чтв 17:51:38 247061771273
друзь.png 840Кб, 1194x829
1194x829
>>247034324 (OP)
>1000-этажное здание
Это уже стратосфера, я умираю.
20/05/21 Чтв 17:55:07 247062019274
log2 - вот минимальное колво иттераций. Действительно за 4 шага можем найти. искал бинарным путем
20/05/21 Чтв 17:57:37 247062176275
20/05/21 Чтв 17:58:06 247062214276
>>247062019
>log2n
ТОЧНО ПОСЛЕДНИЙ ФИКС
Аноним 20/05/21 Чтв 18:00:31 247062368277
>>247060522
Если ты сделал второй из этих бросков в а+7 и оно не разбилось, тебе придется ещё проверить а+8 и а+9, то есть суммарно будет те же самые четыре броска на один из десятки. Выбрать один вариант из 9 тремя бросками невозможно просто по теории информации - три броска - это максимум три бита информации, один из 8, а у тебя вариантов больше.
20/05/21 Чтв 18:06:19 247062749278
Programm - binary search
input N:
N=947
Step 1:
N>500
Step 2:
N>750
Step 3:
N>850
Step 4:
N>913
Error: step over than 4. You suck
Отсюда делаем вывод - что задача нерешаема. Достаточно одного контрпруфа, чтобы доказать обсер алгоритма
20/05/21 Чтв 18:07:21 247062812279
Аноним 20/05/21 Чтв 18:10:00 247062993280
>>247059688
Ну а если с 989-го этажа начинает разбиваться? Сколько шагов тогда?
Аноним 20/05/21 Чтв 18:10:51 247063056281
>>247061653
Они неоплодотворённые.
Аноним 20/05/21 Чтв 18:12:25 247063146282
>>247059688
Или с 265 этажа начинает разбиваться, то опиши шаги плиз
Аноним 20/05/21 Чтв 18:33:50 247064568283
>>247062749
Задача нерешаема твоим идиотским способом, придурок. Почему ты решил, что обязательно нужен бинарный поиск, а если он не подходит, то надо жидко пукнуть и обмякнуть? Задачку так-то и линейным можно "решить", худший случай - 999 шагов.

Пиздец, и вот такие животные меня здесь обсирали и чморили, когда я делал робкие попытки вката в айти.
Аноним 20/05/21 Чтв 18:35:35 247064705284
>>247063146
Давай с 265. Яйцо 1 - на 140 не разбилось, на 270 разбилось, два броска. Яйцо 2 - 150, 160, 170, 180, 190, 200, 210, 220, 230, 240, 250, 260 - все не разбились, плюс 12 бросков, итого 14. Яйцо 3 - 264 не разбилось, 267 разбилось, плюс два броска, итого 16. Яйцо 4 - 265 разбилось, плюс один бросок, итого 17. Но я ещё раз повторюсь - это не самый оптимальный алгоритм, мне довольно лень выписывать матрицу оптимального (она будет не очень простой для восприятия).
Аноним 20/05/21 Чтв 18:39:12 247064964285
>>247064568
Ну так они освоили единственный молоток и теперь им всё вокруг кажется гвоздями. Так-то это классная айтишная задача, просто она в первую очередь на рекурсию или лучше даже на динамическое программирование, а не на банальный поиск.
Аноним 20/05/21 Чтв 18:41:15 247065110286
>>247034324 (OP)
>Дано 1000-этажное здание
Можешь со своими школозадачками хуй пососать.
Аноним 20/05/21 Чтв 18:46:06 247065477287
>>247062993
А вот пошагово с 989, у меня настроение хорошее. Первое - 140 270 390 500 600 690 770 840 900 950 не разбилось, 990 разбилось, итого 11 бросков. Второе - 960 970 980 не разбилось, плюс три броска, итого 14. Третье - 984 987 не разбилось, 989 разбилось, плюс три броска, итого 17. Четвертое - 988 не разбилось, итого 18, ответ найден.
Аноним 20/05/21 Чтв 19:12:06 247067133288
>>247052136
НУ ЧЕ ЕБАНЫЕ ПИДОРАСЫ ТАК И НЕ СМОГЛИ ОПРОВЕРГНУТЬ МОЁ ГЕНИАЛЬНОЕ РЕШЕНИЕ, ДА?
Я ЩА ЕЩЁ НАХУЙ ПОСЧИТАЮ СРЕДНЕЕ КОЛИЧЕСТВО ШАГОВ ПРИ МОЕМ РЕШЕНИИ, ЧТОБЫ ВЫ ОХУЕЛИ ГНИДЫ ПОДЗАЛУПНЫЕ
Аноним 20/05/21 Чтв 19:20:56 247067660289
>N-го этажа (или с большей высоты)
Выбрасываю все яйца с 1000 этажа. Или по одному с 1000, 999, 998, 997
Если ни одно не разбилось, то иду вниз, собираю и кидаю снова. А вообще в пизду. Докажи, что это не N-этаж? Не разбилось? Ну и пошёл на хуй.
Аноним 20/05/21 Чтв 19:23:59 247067897290
>>247052136
>>247067133
У тебя даже с банальным случаем 999 что получается? Я правильно понимаю, что больше 40 шагов? А выше есть алгоритм, дающий решение не более чем за 18, так что слюну подотри.
Аноним 20/05/21 Чтв 19:25:42 247067988291
>>247067660
Или ещё решение:
Бросаю все яйца с тысячного этажа на ебало опу. Разбились? Ну и пошёл на хуй под струю мыться. Ведь эмпирически доказано, что задача не решаема.
Аноним 20/05/21 Чтв 19:30:38 247068342292
>>247067897
У меня с банальным случаем 1 сразу же ответ.
А сейчас я пишу тебе развернутый пост, почему я прав, а ты хуйло.
И я ещё посчитаю для каждого этажа количество шагов и найду среднее. Тебе тоже не мешало бы это сделать, иначе твой ротик окажется наполнен моей уриной.
Аноним 20/05/21 Чтв 19:36:11 247068774293
>>247059232
Не растут, а убывают, и не по логарифму, а сложнее. Условно, первый раз ты бросаешь первое яйцо с этажа , который равен (максимум, который можно найти тремя яйцами за 12 бросков)+1. Второй раз - сдвигается вверх на (максимум, который можно найти тремя яйцами за 11 бросков), и так далее. Потом вторым яйцом первый раз кидаешь этажа, который равен (последний установленный безопасный этаж)+(максимальный этаж, который можно установить двумя яйцами за оставшееся количество бросков) и так далее. Оно плохо описывается на пальцах, но вот так.
Аноним 20/05/21 Чтв 19:36:40 247068814294
>>247034324 (OP)
Ответ простой: китайское искусственное гмо яйцо не разобьётся нискакова этажа, а просто отпрыгнет в лоб ученому
Аноним 20/05/21 Чтв 19:39:25 247069044295
>>247068342
Похуй на банальный случай 1, на банальный случай 1 сразу даст ответ вообще линейный поиск. Оптимизация среднего - это классная задача, я согласен, но это НЕ ТА задача, которая поставлена, это в треде уже уточняли, а поставлена задача оптимизации ХУДШЕГО, а худшее у тебя сосет сразу у нескольких решений предложенных в треде.
Аноним 20/05/21 Чтв 19:40:17 247069112296
Аноним 20/05/21 Чтв 19:41:20 247069193297
>>247069044
>Найдите N за минимальное количество бросков.
>не оптимизация среднего

Ты готовь статистику, опущ. Посмотрим.
Аноним 20/05/21 Чтв 19:41:33 247069205298
>>247034324 (OP)
Разделил бы на три, а там от фарта далее также делил на число меньше остатка яиц.
Аноним 20/05/21 Чтв 19:41:51 247069233299
>>247065477
Анонимное уважение!
Интересно, у ОПа есть правильный ответ и пруфы?
Аноним 20/05/21 Чтв 19:44:54 247069456300
>>247034324 (OP)
Беру два яйца и кладу их ОПу на лицо, постукивая хером по лбу за такие ёбнутые задачи
Аноним 20/05/21 Чтв 19:46:23 247069555301
Двач действительно деградировал. Кидаешь яйцо на первом этаже, если не разбилось - идёшь, подбираешь, кидаешь на втором
/thread
Аноним 20/05/21 Чтв 19:47:06 247069611302
>>247069555
Оно и с первого блять разобьется.
Аноним 20/05/21 Чтв 19:47:31 247069645303
>>247069555
>минимальное количество бросков
Ты не очень умный, да?
Аноним 20/05/21 Чтв 19:47:53 247069670304
>>247069611
N=1, поздравляю с решением
Аноним 20/05/21 Чтв 19:48:48 247069722305
>>247069193
>>247039405
В тексте не написано, минимальное что имеется в виду, а вот уточнение по этому поводу. Впрочем, ты считай свое среднее, считай. Гарантирую, что ты отсосешь более чем у одного решения в треде даже по среднему, если, конечно, не начнёшь бегать и кричать без оснований, что распределение искомых этажей на самом деле не равномерное.
Аноним 20/05/21 Чтв 19:49:14 247069750306
>>247069645
Один раз это уже слишком много? У меня бля из холодильника яйцо падает и разбивается, а тут с первого этажа блять.
Аноним 20/05/21 Чтв 19:49:53 247069790307
>>247034324 (OP)
Первое яйцо кидаем с высоты хn+1=(верхнийэтаж-xn)/ln(верхнийэтаж-xn)
После того как разобьётся кидаем линейно с приростом в единицу, пока не разобьётся, соотвественно предыдущий перед разбитием этаж будет искомым.
Для поиска достаточно двух яиц.
Чтобы использовать все четыре яйца - итерацию с логарифмом можно повторить перед линейным поиском при разбитии два раза.
Аноним 20/05/21 Чтв 19:50:53 247069865308
>>247069205
Хотя не. На два. Допустим 500 этаж, бьётся, делим на два, но ниже, то есть пробуем с 250, не бьётся, пробуем с 750-го.
И далее проверяем также по остатку яиц: 250 не бьётся, то 125 пробуем, если бьётся, то с 375-го, как пример итерации.
Аноним 20/05/21 Чтв 19:51:04 247069880309
15718384301933.jpg 90Кб, 677x823
677x823
>>247034324 (OP)
Да, яйцо и с первого разобьется, ты дурак чтоль?
Аноним 20/05/21 Чтв 19:55:55 247070188310
>>247069645
Ну для того, чтобы точно определить этаж, минимум 9 бросков, меньше никак
Аноним 20/05/21 Чтв 19:57:00 247070259311
>>247069865
Короче, ОП-хуй, загадывай число от 1 до 1000, буду по своему алгоритму в треде кидать.
Аноним 20/05/21 Чтв 19:59:20 247070363312
>>247069865
Почти правильно, только замени 500 на 512, 250 на 256, и так далее, получится сносный алгоритм
Аноним 20/05/21 Чтв 20:00:54 247070483313
>>247069865
>Допустим 500 этаж, бьётся, делим на два, но ниже
500
Разбилось.
250
Разбилось.
125
Разбилось.
62
Разбилось.

Яиц больше нет.
Аноним 20/05/21 Чтв 20:01:19 247070499314
>>247069790
Проебался
хn+1=xn+(верхнийэтаж-xn)/ln(верхнийэтаж-xn)
Аноним 20/05/21 Чтв 20:03:16 247070571315
>>247034324 (OP)
Кидаю с 16.
Разбилось - трех яиц хватит на поиск этажа (8,4,2).
Если не разбилось - спускаюсь, подбираю это яйцо и кидаю с 32.
Аноним 20/05/21 Чтв 20:03:51 247070582316
>>247070363
Только у нас килоэтажное здание, а не кибиэтажное, потому удобнее работать с десятичными приставками, а не двоичными.
Аноним 20/05/21 Чтв 20:03:57 247070588317
>>247034324 (OP)
>У вас есть четыре яйца.
Вообще-то два.
Аноним 20/05/21 Чтв 21:29:03 247071052318
>>247034324 (OP)
Ну давай покумекаем.
Одним броском яйца со среднего (в нашем случае 500-го) этажа можно гарантированно сузить круг поисков вдвое. Двумя бросками его можно сузить втрое, если начинать снизу, то есть с 333-го этажа: если разобьётся, то искомый этаж надо искать в нижней трети, если яйцо целое: кидаем с 667-го этажа и получаем либо среднюю, либо верхнюю треть. Таким макаром можно делить дом на любое число частей Х, но при этом мы на каждое деление мы в наихудшем случае будем тратить Х-1 бросков и 1 яйцо. Так как яец у нас всего две пары, мы должны поделить 1000 этажей 4 раза так, чтобы в итоге знать единственный нужный этаж, то есть 1000/Х1Х2Х3Х4=1. Теперь понятно, что произведение этих "разделений" должно быть больше или равно 1000, то есть задача сводится к тому, чтобы разложить тысячу на 4 множителя так, чтобы их сумма была минимальна. Такую комбинацию найти несложно, это три шестёрки и пятёрка - будет 1080. Не забудем отнять единицу от каждого из них, чтобы найти число бросков, и получим окончательный ответ 5+5+5+4=19.

Конкретный алгоритм будет выглядеть как-то так:
1. Отправляем яечко на встречу с асфальтом с 167-го этажа. Если оно бьётся, значит мы сэкономили 4 броска, но нас это не интересует, потому что мы ищем только худшие расклады, поэтому яйцо остаётся целым и мы кидаем его с 333, 500, 667 и 833 этажей.
2. Теперь мы знаем промежуток в 167 этажей, где спрятан заветный этаж N. Дальше будем делить на шесть: отсчитываем с нижней границы промежутка 28 этажей, потом 56, 84, 111 и 139. Получаем промежуток в 28 этажей.
3. Дальше по плану 5, 9, 14, 19 и 23 этажи от нижней границы промежутка.
4. Последнее яйцо, последние 5 этажей. Просто перебираем по одному снизу вверх.

Тред не читал, может кто-то уже решил, может я обосрался, но мне в принципе похуй, я доволен собой.
Аноним 20/05/21 Чтв 21:47:08 247072234319
>>247067897
>А выше есть алгоритм, дающий решение не более чем за 18, так что слюну подотри.
Покажи.
И для 999 будет 25 шагов.
Аноним 20/05/21 Чтв 21:48:54 247072360320
>>247070571
> Если не разбилось - спускаюсь, подбираю это яйцо и кидаю
А чё, так можно было?
Аноним 20/05/21 Чтв 21:49:12 247072379321
Аноним 20/05/21 Чтв 21:53:18 247072632322
>>247072234
Пока макаба шаталась я докорректировал. В среднем получается 24 шага.

https://ideone.com/BrgL5E код тут
Среднее: 24.412
Максимум: 77

Поясняю ушлёпинам. Это сокращение диапазона бинарным поиском.
У нас есть число N, оно от 1 до 1000. То есть в нём 10 разрядов.
Начинаем бросать с 1 этажа, затем со 2, и так далее, с 2^n этажа. Как только яйцо разобьётся, мы будем знать ещё что на предыдущей попытке оно ещё не разбилось.

Пусть N = 00111 01011

Тогда яйцо разобьётся на 01000 00000 этаже. И тем самым мы будем знать, что N где-то между 00100 00000 и 01000 00000 этажом.
А это значит, что N имеет вид 001xx xxxxx. Мы затратили на это 8 шагов: 7 разряд старшего бита + 1 разряд, при котором яйцо разбилось.

Дальше нам остаётся открыть оставшиеся неизвестные биты. Пойдём тем же бинарным поиском дальше и возьмём половину от неизвестного диапазона.
То есть проверим, будет ли старший неизвестный бит 0 или 1. Если разбилось, то значит что N меньше текущего предположения, и в старшем неизвестном 0. Если же оно не разбилось, то поднимаемся ещё выше и пробуем снова.
Таким образом мы доходим до 00111 xxxxx. После старшего бита мы открыли 2 единицы. Сейчас на 3 шаге яйцо разобьётся, потому что в старшем неизвестном бите 0, а мы будем на 00111 1xxxx этаже. То есть мы затратили шагов (количество единиц в первой серии - 1(старший бит)) + 1 шаг, на котором яйцо разбивается. Можем сократить -1+1 в 0. Получится, что для 2 яйца мы затратили 3 шагов: количество единиц в первой серии.

Аналогично для третьего яйца. Сейчас мы имеем 00111 0xxxx. Пробуем. Получаем 00111 01xxx. Ещё раз, и яйцо разбивается, так как мы на 00111 011xx этаже, а N = 00111 010хх. Затратили 2 шага: количество единиц в 1 серии + 1 шаг, на котором яйцо разбивается.

Теперь имеем 00111 010хх. Оставшиеся 2 бита придётся открывать перебором. Мы знаем, что там будет 11, то есть перебираем 00, 01, 10, 11 и на 4 шаге яйцо разбивается. 4 шага это число из цифр, младших второй серии единиц, то есть стоящих после второго старшего 0 в числе + 1 шаг, на котором яйцо разбивается.

В сумме имеем 4 слагаемых: разряд старшего бита + 1 + количество единиц в первой серии + количество единиц во второй серии + 1 + число из цифр правее второго ноля + 1. При этом между сериями не может быть больше разрыва, чем один ноль.
Если же на каком-то этапе число заканчивается, то подсчёт слагаемых тоже оканчивается, так как в этом случае мы сразу попадаем на ответ.

Также не забываем, что будет, если мы поднимемся до 512 этажа, а яйцо всё ещё не разбивается. Мы получаем возможность сократить интервал уже не двумя, а тремя яйцами. То есть в этом случае надо будет искать по 3 серии единиц (с максимальными разрывом в один 0)
Аноним 20/05/21 Чтв 21:55:26 247072772323
>>247067897
Ну теперь давай ты мне покажи, где у тебя в среднем будет 18, умник.
Аноним 20/05/21 Чтв 21:57:02 247072883324
16215281569270.png 15Кб, 880x512
880x512
>>247047196
КИДАЕШЬ С ТРЕТЬЕГО ЭТАЖА
@
РАЗБИВАЕТСЯ
@
КИДАЕШЬ С ДЕСЯТОГО ЭТАЖА
@
НЕ РАЗБИВАЕТСЯ
@
ЗНАЧИТ ТАК БЛЯДЬ
Аноним 20/05/21 Чтв 21:58:49 247072991325
>>247072632
>Найдите N за минимальное количество бросков
>В среднем получается 24
С какого тебя этажа в младенчестве бросали, что ты теперь не понимаешь разницы между минимальным необходимым и средним?
Аноним 20/05/21 Чтв 22:03:23 247073291326
>>247072360
Ну вроде не говорили, что нельзя. Яйцо-то целое.
Аноним 20/05/21 Чтв 22:07:46 247073578327
>>247072991
Ты понимаешь, что минимальное будет в случае алгоритма, дающего минимальное среднее? Как ты блять заранее определишь каким именно алгоритмом тебе пользоваться, чтобы нормально подстроиться под загаданное число и не попасть в худший случай, вероятность которого может быть высока?
Аноним 20/05/21 Чтв 22:09:54 247073719328
>>247072991
Ты просто блять обмудина ебаная, я тебя ненавижу пидорас
Аноним 20/05/21 Чтв 22:10:21 247073750329
>>247072991
Никогда больше не заходи в подобные треды козлина ебучая
Аноним 20/05/21 Чтв 22:11:44 247073864330
>>247072991
Я могу кидать с N этажа каждый раз, а потом с N-1 и тратить на поиск 2 шага. И хули? Как тебе такое, говно?
Аноним 20/05/21 Чтв 22:16:17 247074177331
>>247046021
Пошел и купил бы больше яиц дегенерат ебучий, алгоритмы ему нужны лол
Аноним 20/05/21 Чтв 22:18:01 247074302332
>>247074177
Я те дам щас, продукты он переводить удумал! Лучше бы нам отдал!
Аноним 20/05/21 Чтв 22:18:44 247074354333
>>247072632
Э, бля, у нас тут новые вводные. Неразбившееся яйцо можно перебрасывать.
Аноним 20/05/21 Чтв 22:19:05 247074378334
>>247072234
Вот тебе алгоритм, дающий худшее (не среднее даже, а худшее!) в 18.
>>247054859
Аноним 20/05/21 Чтв 22:20:17 247074483335
Аноним 20/05/21 Чтв 22:21:22 247074561336
>>247044833
> Здание, по-умолчанию, это постройка для жизнедеятельности человека
Яйцо по умолчанию находится в твоей жопе
Аноним 20/05/21 Чтв 22:21:59 247074623337
>>247044833
> Здание, по-умолчанию, это постройка для жизнедеятельности человека
Тыскозал? А если оно не для людей делалось тупень? У тебя же яйца не для них
Аноним 20/05/21 Чтв 22:22:51 247074682338
>>247074483
После обращение ставится запятая. Если яйцо не разбилось, то ты его сожрал?
Аноним 20/05/21 Чтв 22:23:29 247074729339
>>247054771
Кто тебе сказал что у тебя имеются мозги в голове а не просто пустота, хуила ебаная?
Аноним 20/05/21 Чтв 22:25:04 247074850340
>>247043526
> работает медленно
> подняться на 1й этаж
> скинуть
> у 99% других анонов в треде яйца начинают бросать с 999
Аноним 20/05/21 Чтв 22:29:27 247075177341
16128652538940.png 292Кб, 493x421
493x421
О, меня разъебали на собеседовании похожей задачей, только с двумя яйцами. Сложность алгоритма будет корень 4 степени из N, что лучше одного яйца с O(N), но хуже бинарного поиска с O(logN).
Если коротко, то первым яйцом кидаем: 100, 200, 300 и тд, пусть это будет 400 этаж. Дальше вторым яйцом начинам кидать с 410, 420... И так далее. Только ОП еблан, в этой задаче для красивого ответа с десятками и сотнями должно быть 3 яйца, именно в его варианте здесь шаг для последнего яйца будет от 5 до 6.
Даже после обосрамса на собесе на работу взяли!
Аноним 20/05/21 Чтв 22:33:02 247075464342
hIOjucNEQ9g.jpg 313Кб, 982x1080
982x1080
>>247034324 (OP) Ебать тред полон аутистов.
Бросаем по одному с 16го, 32го, 48го и так далее. Как яйко разбилось, то оставшиеся бросаем сразу ниже на 8, 4 и 2 этажа. Итого тратим до 66 бросков и 4 яйца.
Аноним 20/05/21 Чтв 22:40:22 247075983343
Вы ебанутые, блядь? Яйца с первого же этажа кокаются
Аноним 20/05/21 Чтв 22:44:17 247076259344
>>247075464
Есть простейшие алгоритмы, которые сделают лучше, чем за 66 в худшем случае и за меньшее количество яиц, вот прям простейшие. Например, первое яйцо кидаешь на 100, 200, ..., 1000 (не больше 10 бросков). Пусть разбилось на этаже р1, а последним этажом, где не разбилось, был к1=р1-100. Тогда второе кидаем на к1+10, к1+20, ..., к1+90 (не больше 9 бросков). Пусть разбилось на этаже р2, а последним, где второе не разбилось, был к2=р2-10 (если второе яйцо вообще не разбилось, то р2=к1+90). Теперь кидаем третье яйцо с к2+1, к2+2, ..., к2+9 (не более 9 бросков). Очевидно, что им мы найдем искомый этаж, затратив суммарно не более 28 бросков и не более трёх яиц, что очевидно лучше твоих 66 и четырёх.
Аноним 20/05/21 Чтв 22:45:11 247076326345
Тред не читал. Короче f(k,n) - оптимальное число попыток для k яиц и n этажного дома. Очевидно, что если есть одно яйцо, то попыток f(1,n)=n. Очевидно, если ноль этажей то попыток f(k,0)=0. Дальше хуже, пусть первый бросок с этажа j, тогда яйцо либо разобьётся и тогда попыток f(k-1,j-1)+1, либо не разобьётся и тогда нужно будет сделать попыток f(k, n-j)+1. Из этих вариантов нужно выбрать худший. Итого имеем f(k,n)=min_{j=1..n} max(f(k-1,j-1)+1,f(k,n-j)+1). Сам я это в рот ебал считать, написал программу, говорит что f(4,1000)=13.
Аноним 20/05/21 Чтв 22:46:14 247076394346
Аноним 20/05/21 Чтв 22:48:22 247076590347
Аноним 20/05/21 Чтв 23:06:53 247077908348
Бамп годному треду
Аноним 20/05/21 Чтв 23:10:42 247078194349
>>247060872
> "кинули сначала на каждом сотом, потом на каждом десятом, потом на каждом первом"

Если нужный этаж 999, то ты проебешь все яйца на 400 этаже и если попробовать спасти ситуацию будешь по 1 считать до 999 с 301, что даст тебе 499 попыток в худшем варианте
Аноним 20/05/21 Чтв 23:27:42 247079333350
>>247078194
Ну, да, естественно имелось в виду не прям на каждом-каждом, а на каждом подозрительном. То есть первое кидаем до тех пор, пока не разобьётся, на каждом сотом этаже, второе кидаем не прям на каждом десятом, а на каждом десятом, начиная с того сотого, где первое яйцо последний раз не разбилось, третье кидаем не прям на каждом первом, а на каждом первом, начиная с того десятого, где второе последний раз не разбилось.
Настройки X
Ответить в тред X
15000
Макс объем: 20Mб, макс кол-во файлов: 4
Кликни/брось файл/ctrl-v
X
Ваш шидевор X
Стикеры X
Избранное / Топ тредов