>Дано 1000-этажное здание. Если яйцо сбросить с высоты N-го этажа (или с большей высоты), оно разобьется. Если его бросить с любого меньшего этажа, оно не разобьется. У вас есть четыре яйца. Найдите N за минимальное количество бросков.
Рандомная хуйня. Берем худший случай - 124ый этаж. Скидываем одно с 500го, разбивается. Скидываем с 250го, та же хуйня. Скидываем со 125го. Остается одно яйцо, последовательно кидаем 123 раза, начиная с 1го. Итого 126 бросков максимум.
Кидаем с пятисотого этажа, если разбилось кидаем с 250-го, если снова разбилось кидаем с 125 этажа, если разбилось кидаем с 75 этажа, если разбилось кидаем с первого до 75-го поочередно, пока не разобьётся Все случаи расписывать лень, но смысл решения понятен
>>247034797 Есть лучше. Берем худший случай 999 этаж. Кидаем с 100го, с 200го, с 300го и т.д. С 1000го разбивается. Начинаем кидать с 900 до 999. Итого 10 + 99 = 109 бросков. Осталось придумать как выбрать промежутки вместо 100 с учетом 4ех яиц
>>247035078 Анон, ты гений. Но у тебя после броска с 1000го еще 3 яйца, поэтому можно бросить с 950го, 975го и т.д. Итого для 999го этажа выходит 15 или 16 бросков, в зависимости от выбора середины на нечетных этажах.
>>247035297 Я про это и писал. >Осталось придумать как выбрать промежутки вместо 100 с учетом 4ех яиц Там не факт что сразу надо кидать по 100, может есть оптимальнее вариант
>>247035638 Таким образом можно абстракцией назвать любой нелогичный бред. Задача содержит в себе условие, что это именно яйцо и его разбиваемость при определенных условиях - тоже его неотъемлемый атрибут, а никакая не абстракция.
>>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, так как не проверял
>>247035638 >Челики, неспособные в абстракцию. Кого ебут твои абстракции в реальном мире. Тебе ставят задачу - узнать с какого этажа разобъется яйцо. Правильный ответ - с первого.
>>247034324 (OP) Двачеры это никогда не решат, потому что это задача на оптимизацию из функционального анализа, 4 курс физмата, причём злоебучего. Я тоже не решу, потому что от 4 курса я уже дальше многих местных обитателей.
Алгоритм для 100-этажного здания уже давно придуман, максимальное количество шагов в нём равно 14. Значит, для 1000-этажного после этих 14 шагов нужно будет найти число внутри нужного десятка. Итого ещё 5 шагов, итого 19.
>>247035219 Не в любом. Ты принимаешь, что худший случай - это 999 этаж, а на самом деле худший случай зависит от метода (и лучший тоже). Пусть у тебя яйцо бьётся на 751 этаже. Тогда метод с делением пополам даст тебе четыре броска (с 500 - не разбилось, с 750 - не разбилось, с 875 - разбилось, с 751 - разбилось), метод отсчитывать сотни будет заведомо хуже (не менее восьми бросков точно). Тут ещё очевидно кривое условие задачи - при фиксированном методе минимально возможное количество бросков будет зависеть от того, на каком этаже яйцо бьётся, собственно, если яйцо бьётся на первом этаже, то оптимальным методом будет "бросать на каждом, если не разбилось - подниматься на один", как ни странно - выяснить вообще первым броском. Так что правильная формулировка тут будет скорее "проводим множество экспериментов с разными яйцами, этажи n распределены равномерно, при каком методе среднее количество бросков будет минимально".
>>247035997 Ну хочешь, это будут не 4 яйца, а 4 дилдака из неизвестного пластикоподобного вещества, которое может разлететься на куски от столкнлвения с землей.
>>247036310 Скорее >>при каком методе наихудшее количество бросков будет минимально". Потому что в другом случае, твоё число в половине случаем не будет выполнять роль минимальности
>>247037711 Да был уже ответ, кидаем 3 попытки деля отрезки этажей попополам, 4м докидываем по одному этажу пока не найдем n , тут по другому и не решишь
>>247034324 (OP) N=1, долбоёб. Ты яйцо последний раз когда в руках держал? Оно даже с высоты пояса разобьётся, но 0,25 этажа нет, а 0 это уровень земли
С какими же кретинами я на одной борде сижу, хосспаде
>>247034324 (OP) Здесь нужно 10 яиц, чтобы узнать этаж, только так можно перекрыть все варианты. Так что в данном случае бинарный поиск - идиотизм, лучше уже просто идти перебором с первого этажа вверх.
Понимаю, что двачеры могут работать только в макдональдсе, но вдруг, кто-то будет ходить по нормальным собесам. Есть похожий вариант задачи, только с другим вопросом. Вопрос может звучать, как:"Как за минимальное количество бросков узнать этаж на котором яйцо разобьется?" Ответ на этот вопрос - как раз таки что за один бросок, когда яйцо разобьется с 1 этажа.
>>247037833 Доказательство оптимальности бы ещё было неплохо увидеть. И, кстати, формулировка задачи кривая, непонятно, что именно мы пытаемся сделать минимальным - наихудшее возможное или среднее ожидаемое? Кажется, что это разные вещи, ведущие к разным стратегиям.
>>247034324 (OP) Если яйцо не разбивается то его можно просто заново кидать с первого по н-ный этаж сколько влезет, все равно меньше попыток чем дрочиться по умному Но всё равно один хуй задача хуевая и оп шалавий выблядок
>>247038503 Дружище, в таком случае, у тебя яйца закончатся раньше чем этажи. Ну хотя может ты свои оторвешь и кинешь, но на 1000 этажей все равно хуй наскребешь так.
>>247036076 >Кого ебут твои абстракции в реальном мире. Программистам, физикам-теоретикам, математикам. Но тебе не пригодится, можешь не переживать на этот счет. Тебе я думаю в жизни нихуя не пригодится, ты ведь долбоёб тупоголовый
>>247034324 (OP) юзаюешь бинарный поиск 3-мя яйцами, пока все не разобьешь. Последним(если понадобиться) идешь последовательно вверх с самого низкого этажа, который получил на первом шаге.
>>247035997 Ну точно дебил... Задача на математику и логику, а не на свойства яиц из реального мира >>247036076 1000-этажные дома тоже в реальном мире существуют?
>>247038259 Двачую. В таких задачах как раз таки суть в вопросах которые задают. Самый лучший расклад, доебаться до вопроса на собеседовании, начать рассказывать какие варианты есть обойти и все такое прочее. Эйчары этого и хотят на самом деле, лол
>>247039405 Тут я вспомнил такие слова как "динамическое программирование". Два игрока: двачер и природа. Природа максимизирует броски, двачер минимизирует.
>>247039174 на самом деле, да. Хуйня. Проще уже пойти так:
1. Кидаем с 500. Понимаем в какой половине наш этаж. 2. Потом идем по сотне. Например 600, 700 и т.д Получаем рейндж в 100 этажей. 3. Броском с середины отрезаем половину.
Получаем 50 этажей проверить последним яйцом + 3 начальных броска. Итого 53. Кто меньше?
>>247039556 Динамическое программирование - это про другое, это когда ты находишь промежуточные решения, сохраняешь их, и дальше решаешь задачу, опираясь на ранее найденные решения
>>247036076 >Кого ебут твои абстракции в реальном мире. Все наше представление о мире - это абстракция. У нас вычислительной силы мозга не хватит не абстрагироваться.
>>247039528 Какая разница, за сколько шагов? Ограничения на количество шагов в задаче нет, его нужно просто оптимизировать. Ты можешь даже одно яйцо кидать с 1, 2, 3, ... N этажа, пока оно не разобьется
>>247039866 >уебок, я ща тебе это яйцо об ебало разобью, ну и где твои учёные в говне моченые, помогли они тебе дебил ебанный? Но ты до сих пор мне ничего не разбил. Выходит, что помогли.
>>247039105 Сам ты дебил. Подобные задачи проверяют логику, именно поэтому там яйцо. Замена яйца на дилдак меняет алгоритм решения. У тебя, по-всей видимости, логика не работает.
>>247041051 >Подобные задачи проверяют логику Если бы это была задача для детсада, то да - логика про хрупкость яйца. Но эта задача для математико-программистов, и тут уже логика про алгоритмы.
>>247040624 >можешь даже одно яйцо кидать с 1, 2, 3, ... N этажа >найдите N за минимальное количество бросков >условия задачи противоречивы и абсурдны сами по себе Всё понял?
>>247039566 Бинарный поиск хорош, когда им можно идти до конца. Если его из-за недостатка яиц придется в какой-то момент прервать, то нужно думать в сторону какого-то другого - определяя нужную треть, четверть или что-то ещё.
>>247034324 (OP) 1. Проверяем сначала граничные значения - кидаем с первого и последнего этажа. Если разбилось на первом - N = 1. Если не разбилось с 1000 - N невозможно определить с текущими условиями. 2. Если после проверки граничных значений нашли, что N между 1000 и 1 - начинаем проверять этажи с первого с шагом в 4. То бишь 1 этаж - 3 этаж - 6 этаж и так далее. На каком-то шаге яйцо разобьется - оставшимися двумя яицами выясняем точный этаж. Например, не разбилось на 120, но разбилось на 123 - кидаем с 121 и 122
>>247041226 Если б это была задача на алгоритмы то вместо яйца была бы переменная, например "предмет" разбивается бла бла бла. И главное в алгоритмах нет нелепых ограничений уровня "у нас было 4 яйца". У меня в простейшей программке для датасаенс 500 миллионов циклов прокручивает при рассчётах и там оптимизация совсем иначе делается. А это банально задачка на бинарный поиск с деревянными как и голова автора условиями.
>>247041051 > Сам ты дебил. Подобные задачи проверяют логику, именно поэтому там яйцо. Так я и написал, что задача на логику, а ты зачем-то начал спорить. То, что изначальные условия задачи нереальны (сверхпрочное яйцо, 1000-этажный дом), не делает саму задачу, ход рассуждений и ее решение нелогичными. > У тебя, по-всей видимости, логика не работает. Ладно-ладно, ты победил
>>247041954 >не делает саму задачу, ход рассуждений и ее решение нелогичными. В рамках задачи все условия должны рассматриваться с точки зрения логики. Этаж может быть отличным от 1? Окей, тогда меням яйцо на пластмассовый дилдак. А пока в условиях яйцо, это неотъемлемая часть условий.
>>247041051 Сукаблядь, бесят школьники и псевдоилитные гречневые гуманитарии. Дано, блядь, задание: найти оптимальный алгоритм. Нет, выёбываются: "Это яйцо, хы хы, оно с первого этажа разобьётся ёпта".
>>247037952 Уже было приведено решение лучше - кидаем первое яйцо с шагом 6^3, второе - с шагом 6^2, третье с шагом в 6. Но это все равно неоптимально.
>>247042929 >Та же задача, с заменой яйца на стеклянный шарик. И чем шарик принципиально отличается от яйца? Мы считаем, что шарик не изменяет структуру после падения и не разобьётся, если его несколько раз сбросить с первого этажа. Мы считаем, что все 4 шарика данные нам одинаковы, хотя в жизни это не возможно. Мы считаем, что разбитие шарика происходит не зависимо от того, в какое место и каким боком он упал. Это все абстракции. И их тут еще миллион, просто мы их принимаем как должное и даже не замечаем, ведь привыкли жить в них.
>>247042868 Так надо и условия задачи ставить соответствующим образом. Ответ для данной констретной задачи - 1. Оптимальный алгоритм найден - яйцо разбивается, упав с 1 этажа, больше искать здесь нечего. Нужен другой алгоритм - меняем предмет на другой.
>>247034324 (OP) после первого неудачного броска останется 3 яйца. с 3 яйцами можно будет определить один из 8 этажей гарантированно, т.е. первое яйцо нельзя бросать с шагом больше, чем 8 этажей. бросаем снизу вверх, это будет 125 бросков+еще 3 в худшем случае. всего 128 бросков в худшем случае
>>247038805 Ты сам даун тупой блять, абстракция нужна чтобы решать РЕАЛЬНЫЕ ЗАДАЧИ. Без этого это нахуй не нужно, понимаешь?
К тебе приходит реальный заказчик и говорит "с какого этажа разобъется яйцо", ты ему отвечаешь "с первого". Ты дал ответ на вопрос, заказчик доволен, отдаёт тебе деньги и уходит.
>>247043337 С чего ты взял, что яйцо разобьётся упав с первого этажа? Куриное яйцо со стандартного дома на Земле разобьется. Но тебе ничего не сказано ни про прочность яйца, ни про высоту этажей, ни про ускорение свободного падения, ни про вязкость воздуха. Почему ты утверждаешь про первый этаж? Установить этаж можно только опытным путем, что и просят сделать.
Потом оказывается, что твоя программа-бросалка яиц делает бешеный перерасход, медленно работает и греет процессоры. А ещё её взломали хакеры и украли все яйца, потому что ты не умеешь в безопасность.
Заказчик уходит к тому, кто умеет решать задачи, а тебя потом ещё в суды таскают.
>>247042868 >Дано, блядь, задание: найти оптимальный алгоритм. Окей. Правильный ответ - шли запрос на ТКП. Подсчитаю затраты на решение задачи, как оплатишь аванс - начнем искать решение.
>>247043316 Я буду считать иначе, т.к. шарик может и не разбиться, упав с 1 этажа. Для решения задачи с шариком алгоритм будет другой. В таком случае, сбрасываем каждый раз с центрального этажа из множества, в котором точно находится искомый этаж. Однако, в условиях яйцо.
>>247043426 >К тебе приходит реальный заказчик и говорит "с какого этажа разобъется яйцо", ты ему отвечаешь "с первого" Кто-то решает и такие простые задачи. Но ведь кто-то должен решать и более сложные? Для них и сделана эта задача в качестве тренировки.
>>247043592 Я тебе говорю про то, что ты хоть с шариком, хоть с яйцом прибегаешь к абстракциям в решении задачи. Без них невозможно решить ни одну задачу.
>>247042863 Окей, давай по-другому. Наверняка ты слышал про Задачу Коммивояжёра. Теперь давай представим, что коммивояжер перемещается между точками не на машине или общ.транспорте, а верхом на велоцерапторе. Тот факт, что велоцерапторы не существуют, как-то меняет логику решения задачи?
Если задачу задать детям в детсаду, они конечно скажут, что задача не имеет решения поскольку велоцерапторы вымерли миллионы лет назад, но мы ведь взрослые люди и понимаем, что задача сводится к поиску алгоритму решения, а не критике самих условий.
Я не знаю, может ты тут путаешь математическую логику и логику из картинок-загадок типа > женщину нашли застреленной в голову, пистолет в руке, было ли это самоубийство или нет? или > Пионеры приехали на речку. Определите сколько пионеров приехало, когда они приехали, на чем они приехали, какая погода
>>247043728 Нет, я ещё прибегаю к намеренной критике долбоёба-составителя задачи. Хочешь выебнуться умом? Составляй задачу умно. Я, как человек, изначально думающий хорошо про людей, пока они не доказали обратное, предполагаю, что автор конкретно такой задачи хотел наебать меня подвохом. Поэтому для поиска того, о чём говоришь ты, я заменил яйцо на шарик. А рассказал про алгоритм в этом случае. Но у ОПа- яйцо.
>>247043052 Ну а 19 - это два яйца на определение с точностью до десятка плюс два яйца на определение окончательной точности. Третьим яйцом можно устроить бинарный поиск, четвёртым - линейный.
>>247044206 Оно может быть и не куриным. Ок, тогда разобъётся максимум с 4 этажа. Найди такое, что не разобъётся? Не бывает? Ты соснул. Каменное яйцо - это не яйцо. Пластиковое - тоже. Это макеты яйца. А по-умолчанию яйцо настоящее. Когда ты пишешь в договоре слово заказчик, ты тоже подразумеваешь, что на самом деле это не заказчик, а "актёр, исполняющий заказчика"? Вот так и в постановке задач следует следить за базаром.
Какие же тут сидят тупорылые животные, хуею просто. ЯЙЦО РАЗОБЬЁТСЯ НА ПЕРВОМ ЭТАЖЕ, МАМ, МАМ, Я РЕШИЛ ЗАДАЧУ С ПОДВОХОМ, А ТУПЫЕ ДВАЧЕРЫ ЧЁ-ТО ТАМ ВЫСЧИТЫВАЮТ СИДЯТ! КСТАТИ, О ДВАЧЕРАХ, НАДО ТРЕД СОЗДАТЬ. ПОМОГИТЕ ВКАТИТЬСЯ В АЙТИ, А ТО ЭТО ЩАС МОДНО, ЧЁ ТАМ ВООБЩЕ НАДО ТИПА ЗНАТЬ И УМЕТЬ?
>>247044554 Здание, по-умолчанию, это постройка для жизнедеятельности человека. Расстояние между этажными перекрытиями не бывает 10 см. Ну а игрушечное здание- это не здание, а макет здания. Обоссан по фактам.
Так бля, тут же надо с 500 потом с 250, 125 и тд кидать, да? Ну или по сотке этажи отсчитывать а потом также десятки ебашить ну и единицы в конце? Пральна? Тред не читал.
>>247044869 Хули ты мне фуфло подсовываешь такое? В условиях яйцо разбивается. Т.е. существует такая принципиальная возможность. Муравьиное не соответствует условиям задачи и превращает её в абсурд.
>>247034324 (OP) 1) Кидаем со второго этажа если разбилось ответ = 1 2) Если не разбилось кидаем с последнего. Если не разбилось значит ответ =1000 3)Если разбилось сбрасываем с 501 этажа. 4)Далее разветвление в зависимости от того разбилось или нет делим верхнюю или нижнюю часть пока не останется одно яйцо. 5)Последним яйцом оставшийся участок проходим снизу пока не разобьётся.
>>247045482 Дружище, посчитай количество ходов в твоем худшем случае и количество ходов в худшем случае других алгоритмов из этого треда. Посиди-подумай, почему ты такая тупая пидораха
>>247045691 Абсолютно то же самое. Тут даже комбинаторикой можно обойтись. Причём если с двумя яйцами и 100 этажами ответ 14, то здесь 13, т.е. ещё меньше.
>>247034324 (OP) ну так и одного яйца хватит если идти от меньшего к большему. Оно ж не разбивается, значит сходил поднял и кидай снова этажиком выше, и так пока не разобьется. В условии сказано, что у меня есть не 4 броска, а 4 яйца, ало.
>>247044455 Понятно что можно, но никто не гарантирует, что это оптимально - и, кажется, неоптимально. Собственно, даже внутри десятка двумя яйцами можно найти не за пять, а за четыре шага (то есть уже не 19, а 18), и совершенно не факт, что определять первыми двумя яйцами именно до десятка - оптимально, а почему не до 17, например?
>>247045935 Понятно, что можно тупо одно яичко ходить и кидать поочерёдно с 1, с 2, с 999 этажа. Вопрос в том, каков наиболее оптимальный алгоритм бросков. Ты в худшем случае кинешь яйцо 999 раз, то есть намудохаешься знатно, пока математик-кун будет стоять рядом и ржать со вспотевшей усталой собаки.
>>247034409 >в 5-ый класс Не верю, потому что для доказательства оптимальности алгоритма нужно проверить вариант с каждым этажом и для каждого алгоритма подсчитать максимум, минимум и среднее количество бросков. Для полного решения задачи надо нахуярить алгоритм, который нагенерирует алгоритмы разбивки на отрезки, и проверит каждый из созданных алгоритмов.
>>247045640 Ну всего два лишних броска которые зато могут сохранить от 3х до 4х яиц. Они либо решают сразу задачу либо позволяют использовать дальше двоичный поиск ведь если ими задача не решается то все 4 яйца остаются целыми..
>>247046242 Разумнее первое кинуть с 333 этажа и вообще работать с третями, а не с половинами. Тогда в самом худшем случае ты 4 яйцами определишь максимум 111 этажей, среди которых находится нужный. А твоим способом так можно определить максимум 125 этажей.
>>247034324 (OP) Кидаю с первого. Если не разобьётся, то со второго, и так пока не найду максимальный этаж. Для поисков придется разбить всего одно яйцо.
>>247034324 (OP) >У вас есть четыре яйца В оригинале их вообще два, машинным вычислением находится за 8 яиц вообще все варианты, задача не имеет смысла без конкретики.
Ебанутый арабский шейх отгрохал новенький 1000-этажный небоскрёб со скоростным лифтом. А ещё он намутил где-то яйца неизвестных науке динозавров, всего 4 штуки. Больше таких нигде нет. Но не забываем начало задачи, он ебанутый, поэтому он хочет эмпирическим путём установить, падение с какого этажа эти яйца способны выдержать. Для этого он вызвал тебя и поставил задачу: придумать способ узнать точный ответ, после чего за полчаса этот способ воплотить в жизнь (то есть поочередное кидание снизу вверх не подходит). Если не придумаешь, тебя ждёт казнь через побивание камнями. После того, как ты дашь ответ, тебя посадят в зиндан, а шейх проверит ответ, посоветовавшись с математиком-индусом. Если ответ неверный или ложный, тебя ждёт жесточайшая смерть с засовыванием колючей проволоки в анус.
>>247045818 Мне не кажется , что прям то же самое. С двумя яйцами ты оптимиизируешь по сути только одну переменную - стартовое количество этажей по первому яйцу, дельта шага первого яйца задана однозначно тем, что у второго шаг может быть только единица. А тут тебе нужно найти стартовый шаг для трёх яиц и дельту шага для двух, это всё же разница.
>>247046564 Если делать так (каждым яйцом искать равные доли), то анон в начале треда правильно заметил, что тогда уж брать корень четвертой степени из 1000 и делать третьим яйцом шаг 6, вторым - 36, первым - 216. Но это неоптимально решение.
>>247034324 (OP) Начать кидать с первого этажа, оно не разбивается, берём его(так как оно целое осталось) и поднимаемся на 2 этаж и так пока не разобьётся итого нашли, потратив всего 1 яйцо
>>247034324 (OP) > У вас есть четыре яйца. Бросаем с 100 этажа начиная повышать на 100 каждый раз.Если разбилось на 500м например то идем на 400й и начинаем 3-м яйцом проверять с 410го повышая на 10 этажей, если разбилось например на 450-м, то идем на 441 и с него 3-е яйцо сбрасываем повышая на 1 этаж каждый раз. 4-е яйцо можно съесть, ибо я хуй знает как задачу оптимизировать вокруг него.
Говно вы тут пишете. А если яйцо не разбилось, но треснуло? Нужно искать только в том интервале, вверху которого оно точно разбилось и внизу которого точно треснуло.
>>247034324 (OP) Кидаю на 500м этаже, не разбивается- поднимаю на 250 этажей, разбивается- опускаю на 250 этажей. Уже на новом этаже по той же схеме сдвигаю еще на 125 этажей. Потом еще на 63, точнее не могу, еще 5 бросков и я установлю точную границу этажа, где разобьется или нет.
>>247034324 (OP) Лол, я понял, НАСКОЛЬКО задача становится проще, если ее перевернуть наоборот. Не "задано число яиц и этажей, определить число попыток", а "задано число яиц и попыток, определить максимальный этаж", после этого решается примерно на изи.
>>247049318 Три этажа максимум, в чем проблема? Первый бросок со второго этажа, если разбилось - то второй бросок с первого. Если не разбилось - то второй бросок с третьего. Два яйца при любом раскладе лишние, бывает.
Кидаем на 50. Если не разбилось - идем выше. Разбилось - ниже. Кидаем на 25 или 75. Повторяем процедуру, разделяя промежуток на две части. Когда остается одно яйцо, а остальные разобьются - берем нижний предел промежутка и начинаем бросать каждый раз поднимая на 1. На каком разобьется - тот этаж - это искомое N.
>>247034324 (OP) Ну сначала кидаешь с середины здания, то есть с 500 этажа. Если разбилось, то с середины той половины, что ниже этажа, с которого кидал. Если не разбилось, то с середины верхней половины. Так повторяешь пока не разобьешь все яйца кроме одного, им прокидываешь по одному этажу снизу вверх оставшийся интервал.
Худший сценарий: 1. Идем с шагом 200 (4 попытки, бьем одно яйцо) 2. Идем с шагом 50 (3 попытки, бьем одно яйцо) 3. Идем с шагом 16 (2 попытки, бьем одно яйцо) 4. Оставшиеся 15 этажей последовательно проверяем последним яйцом.
Первые 3 яйца для нахождения нижней планки, считаем что она стремится к 0. Кидаем первое яйцо с 1 этажа, если не разбилось то со 2, 4, 8 и так далее, пока не разобьётся на этаже Z. Соответственно нашли старший бит числа N, то есть знаем, что N лежит между Z/2 и Z. Затем выбираем половину в этом диапазоне, Z/2+Z/4. Если не разбилось, снова поднимаем этаж на вдвое меньший. Повторяем, пока второе яйцо не разобьётся. Этим уточнили интервал – он между этажом в предыдущей попытке и текущей. Аналогично третьим яйцом ещё раз сокращаем доступный предыдущий диапазон. Четвёртым яйцом с нижней границы полученного диапазона проверяем каждый этаж, поднимаясь выше.
>>247050837 Что значит "тоже"? Если оно разбилось на втором, то вторую попытку пускаем на проверку первого этажа. Если на втором НЕ разбилось - то тогда кидаем с третьего, если на третьем разбилось - то мы выяснили, что бьётся начиная с третьего и выше, не разбилось - хз, бьётся где-то высоко, не можем сказать (собственно, не совсем корректно сформулировал обратную задачу, да - при заданном числе яиц и попыток назвать максимальное n такое, что если яйцо бьётся при броске с n-ного этажа и выше, то мы можем экспериментально установить это n - в такой формулировке n=3, если яйцо бьётся при броске с минимум первого, второго или третьего, то мы это экспериментально проверим, если при броске минимум с четвертого или больше - то нет).
Покормлю. Представим здание как отрезок длиной N на котором могут находится натуральные числа. Делим его на 4 равные части (нужно провести три границы для этого). С каждой начерченной границы выкидываются по одному яйцу. Далее выбирается новый отрезок между границами где одно яйцо разбилось (высокая грань) и где не разбилось. Собираем оставшиеся яйца и делим выбранный отрезок на k равных частей (k - количество оставшихся яиц) и повторяем тот же алгоритм. Если k равно 1, то идем от нижней грани до высшей с шагом 1 (тут уж ничего не поделаешь). Надеюсь понятно объяснил.
>>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, как у тебя.
>>247054731 Тогда дели на грани этаж 100, 300, 600, (ну и последний 1000). Дальше найдя нужный отрезок дели его оставшимися яйцами по похожим соотношениям.
>>247056029 Эм. Где ты тут видишь равные соотношения? Говорю первое выкидывается с 100. Если не разбилось - с 300, если и не разбилось дальше - то с 600. А если на каком-то разбилось то берем отрезок между двумя гранями и делим по такому же принципу. Если интересно почему принцип таков, то напишу вот такое уравнение: x + 2x +3x +4x = 1000 10x=1000 x=100
Первая грань 100, вторая на 2x больше (300), третья на 3x больше (600).
>>247034324 (OP) Пизда двачеры тупые. Вам не сказано какая высота дома, соответственно не факт что с первого этажа если кинуть - оно разобьется. Ответ: кидать по очереди с первого этажа. Разобьется с этажа N-1.
Задача хуйня для лошков. Поехали с задачей посерьёзнее. Дано m-этажное здание. Если яйцо сбросить с высоты N-го этажа (или с большей высоты), оно разобьется. Если его бросить с любого меньшего этажа, оно не разобьется. У вас есть n яиц. n < m. Найдите N за минимальное количество бросков.
>>247034324 (OP) Какой уебан придумывает эти ебанутые аналогии с яйцами и небоскребами? НАЙДИ Х В ДИАПАЗОНЕ ОТ 1 ДО 1000, БЛЯДЬ Какие этажи сука, наркоман
126 бросков Кидаем с 500, разбиваем, кидаем с 250, разбиваем, кидаем со 125, разбиваем. Оставшимся ейцлм проходим с 1 до 123, этого достаточно, и того 123+3=126 Если на каком-то из пунктов яйцо не разбивается, то будет меньше бросков, чем в этом случае. Это худший случай, а потому исчерпывающий. Все формально доказывать мне лень. Алгоритм: начинаем с 500, кидаем, далее делим пополам верхнюю пятихатку, если не разбилось и кидаем с 750, а если на 500 разбилось, то кидаем с 250. Так делим на два наш промежуток и кидаем, пока не останется одно яйцо. Этим яйцом проходим с самого высокого этажа где не разбилось до самого низкого, где разбилось. Это точно не больше 123
>>247059343 Мой алгоритм работает. Выше у быдла получается больше бросков при крайних значениях типа н 999 или н 1 Принимаю претензии и критику в отношение моего алгоритма.
>>247058621 У нас в здании всего 1000 этажей, то есть тебя смущают варианты 999 и 1000 только. В любом из них я делаю 11 бросков первым яйцом, узнаю, что на 990 оно не бьётся, а на 1000 уже бьётся, вторым яйцом делаю ноль бросков (мне и так известна десятка этажей), третье яйцо кидаю на 994, 997 и 999 (14 бросков). Если яйцо не разбилось на 999, то ответ - 1000, этот этаж я проверил первым яйцом. Если яйцо разбилось на 999, то я бросаю четвертое яйцо с 998 и по результатам этого броска говорю 998 или 999 (итого 15 бросков).
>>247059592 Это худший случай, прочитай весь пост. Если не разбиваем, то кидаем с 750, далее либо с 625 либо с 875 и т.д, пока не останется одно яйцо, которым мы проходим по всему диапазону от максимального неразбившегося до минимального разбившегося. Я бля в посте том все это расписал
>>247054859 Неплохо. Мимо автор говна с 126 бросками У тебя даж 17 получится, ибо когда знаем а и а+10, между которыми искать, мы за 3 броска найдём среди 9 оставшихся нашу хуйню. Один в а+5, воторой либо в а+2 либо в а+7, ну и третий понятно куда.
>>247034797 > Остается одно яйцо, последовательно кидаем 123 раза, начиная с 1го. Нахуя? Лучше снова делать по половине. Т.е. кинуть с 62 этажа, потом с 93 и тд.
>>247059644 Даже банальный алгоритм уровня "кинули сначала на каждом сотом, потом на каждом десятом, потом на каждом первом" даст не более 30 бросков в худшем случае, против твоих в худшем случае 123. И как раз для 999 этажа бросков у тебя будет овердохера.
>>247060522 Если ты сделал второй из этих бросков в а+7 и оно не разбилось, тебе придется ещё проверить а+8 и а+9, то есть суммарно будет те же самые четыре броска на один из десятки. Выбрать один вариант из 9 тремя бросками невозможно просто по теории информации - три броска - это максимум три бита информации, один из 8, а у тебя вариантов больше.
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 Отсюда делаем вывод - что задача нерешаема. Достаточно одного контрпруфа, чтобы доказать обсер алгоритма
>>247062749 Задача нерешаема твоим идиотским способом, придурок. Почему ты решил, что обязательно нужен бинарный поиск, а если он не подходит, то надо жидко пукнуть и обмякнуть? Задачку так-то и линейным можно "решить", худший случай - 999 шагов.
Пиздец, и вот такие животные меня здесь обсирали и чморили, когда я делал робкие попытки вката в айти.
>>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. Но я ещё раз повторюсь - это не самый оптимальный алгоритм, мне довольно лень выписывать матрицу оптимального (она будет не очень простой для восприятия).
>>247064568 Ну так они освоили единственный молоток и теперь им всё вокруг кажется гвоздями. Так-то это классная айтишная задача, просто она в первую очередь на рекурсию или лучше даже на динамическое программирование, а не на банальный поиск.
>>247062993 А вот пошагово с 989, у меня настроение хорошее. Первое - 140 270 390 500 600 690 770 840 900 950 не разбилось, 990 разбилось, итого 11 бросков. Второе - 960 970 980 не разбилось, плюс три броска, итого 14. Третье - 984 987 не разбилось, 989 разбилось, плюс три броска, итого 17. Четвертое - 988 не разбилось, итого 18, ответ найден.
>>247052136 НУ ЧЕ ЕБАНЫЕ ПИДОРАСЫ ТАК И НЕ СМОГЛИ ОПРОВЕРГНУТЬ МОЁ ГЕНИАЛЬНОЕ РЕШЕНИЕ, ДА? Я ЩА ЕЩЁ НАХУЙ ПОСЧИТАЮ СРЕДНЕЕ КОЛИЧЕСТВО ШАГОВ ПРИ МОЕМ РЕШЕНИИ, ЧТОБЫ ВЫ ОХУЕЛИ ГНИДЫ ПОДЗАЛУПНЫЕ
>N-го этажа (или с большей высоты) Выбрасываю все яйца с 1000 этажа. Или по одному с 1000, 999, 998, 997 Если ни одно не разбилось, то иду вниз, собираю и кидаю снова. А вообще в пизду. Докажи, что это не N-этаж? Не разбилось? Ну и пошёл на хуй.
>>247052136 >>247067133 У тебя даже с банальным случаем 999 что получается? Я правильно понимаю, что больше 40 шагов? А выше есть алгоритм, дающий решение не более чем за 18, так что слюну подотри.
>>247067660 Или ещё решение: Бросаю все яйца с тысячного этажа на ебало опу. Разбились? Ну и пошёл на хуй под струю мыться. Ведь эмпирически доказано, что задача не решаема.
>>247067897 У меня с банальным случаем 1 сразу же ответ. А сейчас я пишу тебе развернутый пост, почему я прав, а ты хуйло. И я ещё посчитаю для каждого этажа количество шагов и найду среднее. Тебе тоже не мешало бы это сделать, иначе твой ротик окажется наполнен моей уриной.
>>247059232 Не растут, а убывают, и не по логарифму, а сложнее. Условно, первый раз ты бросаешь первое яйцо с этажа , который равен (максимум, который можно найти тремя яйцами за 12 бросков)+1. Второй раз - сдвигается вверх на (максимум, который можно найти тремя яйцами за 11 бросков), и так далее. Потом вторым яйцом первый раз кидаешь этажа, который равен (последний установленный безопасный этаж)+(максимальный этаж, который можно установить двумя яйцами за оставшееся количество бросков) и так далее. Оно плохо описывается на пальцах, но вот так.
>>247068342 Похуй на банальный случай 1, на банальный случай 1 сразу даст ответ вообще линейный поиск. Оптимизация среднего - это классная задача, я согласен, но это НЕ ТА задача, которая поставлена, это в треде уже уточняли, а поставлена задача оптимизации ХУДШЕГО, а худшее у тебя сосет сразу у нескольких решений предложенных в треде.
>>247069193 >>247039405 В тексте не написано, минимальное что имеется в виду, а вот уточнение по этому поводу. Впрочем, ты считай свое среднее, считай. Гарантирую, что ты отсосешь более чем у одного решения в треде даже по среднему, если, конечно, не начнёшь бегать и кричать без оснований, что распределение искомых этажей на самом деле не равномерное.
>>247034324 (OP) Первое яйцо кидаем с высоты хn+1=(верхнийэтаж-xn)/ln(верхнийэтаж-xn) После того как разобьётся кидаем линейно с приростом в единицу, пока не разобьётся, соотвественно предыдущий перед разбитием этаж будет искомым. Для поиска достаточно двух яиц. Чтобы использовать все четыре яйца - итерацию с логарифмом можно повторить перед линейным поиском при разбитии два раза.
>>247069205 Хотя не. На два. Допустим 500 этаж, бьётся, делим на два, но ниже, то есть пробуем с 250, не бьётся, пробуем с 750-го. И далее проверяем также по остатку яиц: 250 не бьётся, то 125 пробуем, если бьётся, то с 375-го, как пример итерации.
>>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 этажей. Просто перебираем по одному снизу вверх.
Тред не читал, может кто-то уже решил, может я обосрался, но мне в принципе похуй, я доволен собой.
Поясняю ушлёпинам. Это сокращение диапазона бинарным поиском. У нас есть число 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)
>>247072632 >Найдите N за минимальное количество бросков >В среднем получается 24 С какого тебя этажа в младенчестве бросали, что ты теперь не понимаешь разницы между минимальным необходимым и средним?
>>247072991 Ты понимаешь, что минимальное будет в случае алгоритма, дающего минимальное среднее? Как ты блять заранее определишь каким именно алгоритмом тебе пользоваться, чтобы нормально подстроиться под загаданное число и не попасть в худший случай, вероятность которого может быть высока?
>>247044833 > Здание, по-умолчанию, это постройка для жизнедеятельности человека Тыскозал? А если оно не для людей делалось тупень? У тебя же яйца не для них
О, меня разъебали на собеседовании похожей задачей, только с двумя яйцами. Сложность алгоритма будет корень 4 степени из N, что лучше одного яйца с O(N), но хуже бинарного поиска с O(logN). Если коротко, то первым яйцом кидаем: 100, 200, 300 и тд, пусть это будет 400 этаж. Дальше вторым яйцом начинам кидать с 410, 420... И так далее. Только ОП еблан, в этой задаче для красивого ответа с десятками и сотнями должно быть 3 яйца, именно в его варианте здесь шаг для последнего яйца будет от 5 до 6. Даже после обосрамса на собесе на работу взяли!
>>247034324 (OP) Ебать тред полон аутистов. Бросаем по одному с 16го, 32го, 48го и так далее. Как яйко разбилось, то оставшиеся бросаем сразу ниже на 8, 4 и 2 этажа. Итого тратим до 66 бросков и 4 яйца.
>>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 и четырёх.
Тред не читал. Короче 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.
>>247060872 > "кинули сначала на каждом сотом, потом на каждом десятом, потом на каждом первом"
Если нужный этаж 999, то ты проебешь все яйца на 400 этаже и если попробовать спасти ситуацию будешь по 1 считать до 999 с 301, что даст тебе 499 попыток в худшем варианте
>>247078194 Ну, да, естественно имелось в виду не прям на каждом-каждом, а на каждом подозрительном. То есть первое кидаем до тех пор, пока не разобьётся, на каждом сотом этаже, второе кидаем не прям на каждом десятом, а на каждом десятом, начиная с того сотого, где первое яйцо последний раз не разбилось, третье кидаем не прям на каждом первом, а на каждом первом, начиная с того десятого, где второе последний раз не разбилось.