Короче посоны, есть одна задача.У вас есть 1000 бутылок блэйзера, из которых одна отравлена. И только 10 лабораторных мышей. Если мышь выпьет хотя бы нанокаплю отравленного блэйзера, то умрет через сутки. Жидкость из бутылок можно смешивать. Какое минимальное количество суток, за которое можно вычислить бутылку с отравленным блэйзером.И еще вопрос к погромистам, которые наверняка читали про эту хуету и знают ответ: эту хуйню можно алгоритмизировать и юзать вместо бинарного поиска, или это просто частный случай чтоб повыебываться когда кого-то собеседуешь.10 побампаю и свалю.
2/10
3/10
4/10
>>141662634 (OP)Я погромист, не читал про эту хуету, но как только увидел про бинарный поиск – сразу понял решение. Кратко – суть в смешивании одной половины бутылок, определении, в какой из половин яд, а далее по рекурсии.На мой взгляд – обычный бинарный поиск, ничего особенного, чтобы выделить это в отдельный алгоритм.
Трое суток.
>>141662634 (OP)Делим бутылки на 10 групп по 100 бутылок. берём по капле из каждой и смешиваем в 10ти разных банках.Спаиваем каждую мышь ПО ОЧЕРЕДИнаверняка яд будет в 1-5 группе.Далее таким же способом делим 100 бутылок на группы по 10 бутылок.Вычисляем отравленную группу с помощью мышей. Если группу не наши, то прошедшие тест группы оставляем себе, а остальное выливаем.С тебя бутылка блейзера за решение задачи.Желательно, клюквенного.
>>141663019Ты - хуй. Можно на первом шаге разделить все бутылки на 11 равных части по ~91 в каждой, и ценой одной мыши за сутки узнать, какая из частей отравлена.
>>141663140Каюсь, я думал, мыши одноразовые
>>141663229Мыши-то одноразовые, но сдохнет только одна - та, которая выпила неправильную группу, т.к. яд только в одной бутылке.
>>141663019Есть решение как это сделать за сутки. Попозже вкину, если никто не угадает. Просто бинарным поиском там будет 10 суток или меньше, а тут вроде за сутки можно. Вот я подумал что может бинарный поиск уже сосет т.к. что-то лучше придумали.>>141663036Схуяли трое?>>141663059>наверняка яд будет в 1-5 группе.А если нет?>>141663229Мыши одноразовые. Они же умирают.>>141663326Ну и остается группа из 91 бутылки, а какая отравлена не понятно. А на вписку нужно притаранить 999 бутылок и солей, иначе посоны с района пиздюлей дадут.
>>141663655>А если нет?Тогда будет в 6-4 группе.Всё равно отъедет только одна мышь.Схуяли они одноразовые? Это что, тесты на беременность?Что будет, если даже её обмакнуть в блейзер? Да нихуя ей не будет, это же ебучая мышь. Но надо аккуратно. Мыши склонны к алкоголизму.
>>141663655> за сутки можнАх ты-ж сучечка, и правда можно. Нужно дать каплю из каждой бутылки i, мыши j, если i & (1<<j) == 1.
>>141663823Но тогда очень уж дохуя суток уйдет, а хотелось бы побыстрее т.к. посоны ждать не будут.>>141663978Честно говоря уже хуево соображаю и не понял что ты там с шифтом сделал, завтра попробую поиграться с этим делом. А решение вот какое:Пронумеруйте каждую мышь, возьмите 10 стаканов и пронумеруйте их тоже. Далее пронумеруйте каждую бутылку двоичными числами. Поскольку 2 в 10 степени равно 1024, то вам понадобится для этого не более 10 разрядов. Далее каждую бутылку разливаем в каждый из стаканов по следующему правилу: В стакан номер N наливаем из некоторой бутылки, если N-й разряд в её двоичном номере равен 1, и не наливаем, если он равен 0. Например, из бутылки номер 3 наливаем немного вина только в 1-й и 2-й стакан, т.к. двоичная запись числа 3 будет 0000000011. Полученные коктейли даём попробовать мышам с соответствующим номером. Через сутки некоторые мыши умрут. Теперь составим двоичное число, где N-й разряд равен 1, если мышь номер N умерла, и 0 — если осталась жива. Полученное число и будет двоичным номером отравленной бутылки.
>>141662634 (OP)Нумеруешь бутылки двоичным кодом. Десять разрядов как раз хватит на тысячу. Ставишь в ряд десять плошек для мышей. Из каждой бутылки капаешь в плошки, где стоят единицы в двоичном коде. Даешь мышкам. Сдохшие твари выдают тебе двоичный код нужной бутылки.
>>141662634 (OP)Дать одной крысе с интервалом определенным 1000 нанокапель, потом через сутки + интервал крыса умрет. Все ясно?
>>141664440> что ты там с шифтом сделалТо же, что у тебя расписано.Можно ещё ответить на попрос из Оп-поста, что это всё напоминает https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%BB%D1%8C%D1%82%D1%80_%D0%91%D0%BB%D1%83%D0%BC%D0%B0, только здесь так числа подогнаны, что полная определенность.
>>141664528Таки да, правильный ответ.Ну а вместо бинарного поиска это как-то можно использовать?
>>141662634 (OP)А ты неплох, как раз приготовился ответ писать.
>>141664528Достойно, лол. А я только как лох решение на 4ый день получил.типа в первый день выбираешь из 1000, второй из 12, третий из 2 и на четвёртый находишь. Но у меня гуманней - всего 4 мыши сдохнут, а у тебя матожидание от смертей - 5 мышей.
>>141662634 (OP)4 дня. /thread
>>141664895Блять почитал тред. Вы ебанутые? Какой нахуй бинарный поиск? 10 битами можно нахуй закодировать 1024 символа блять, даже больше 1000, вот и все.
>>141664988>типа в первый день выбираешь из 1000после первого дня выбираешь из 100.Быстрофикс
>>141662634 (OP)Тред не читай, сразу отвечай. Эта херня решается быстрее, чем бинарным поиском. Спойлер заключается в кодировании десятичного числа в двоичном коде. Тогда ты за одни сутки вычисляешь бутылку с ядом.
>>141662634 (OP)И да, хотя эту задачу любят давать на прогромистких собеседованиях, сама по себе она - древний боян из ЧГК советских времен, к программированию не имеет никакого отношения.
Разделяем группу из 10 мышей на 2 по 5.Каждый день первой группе мышей даём пробовать по 1 блейзеру. Вторая группа в это время просто живёт и радуется себе. Наступает такая пятёрка блейзеров, один из которых оказывается отравленным. Берём 4 мыши, и по 1 в день даём им попробовать 4 бутылки из смертельной партии. В худшем случае никто не умирает, и у нас остаётся бутылка с ядом. При условии, что яд окажется в последних 5 бутылках, нужно будет потратить 200 дней, +4 дня на определение смертельной бутылки из 5.204 дня! И максимум 2 дохлых мышки.да, идите нахуй, надмозги, мне доставляет так решать, не претендую на самый быстрый вариант
>>141662634 (OP)Динахуй. Я смешаю бутылки по 100 штук. В итоге будет 900 проверенных и 100 хуевых. 100 выбрасываю, 900 бухаю.
Ответ: 1 сутки
>>141664610Н-но посоны просили за сутки подогнать, сказали что если подгоню то с Наташкой с третьего квартала познакомят, а если не подгоню, то пизды дадут.>>141664624В педивикии пустая ссылка, лол. Но все равно спасибо, хотя мне кажется что все-таки это на практике не стоит применять или только в каком-то особенно хитровебанном случае.>>141665061Я хотел узнать можно ли это на практике применять. По кол-ву сравнений, с таким решением, получается ровно 10, а с бинарным поиском 10 или меньше. >>141665208А пиздили, что это толи в яндексе толи в MIT придумали.>>141666347>>141666665>пикрилэтед- Да ты заходи не бойся, ыыы. Ну че принес блэзера? 999 бутылок, как обещал?- Я-я не обе...- Ты смотри, мы пересчитаем. Э! Слыш! Ты чо берега попутал?! Какие все сбухал?! Мыши мои где бля?! Какие 200 дней?! Нна сука!Ладно всем спасибо, я спасть.
>>141667376Не тот пикрелейтед.
>>141662634 (OP)смешиваешь 500 бутылок по капле с каждой - даешь мыши. сдохла\не сдохла, не суть. берешь оставшиеся 500 если сдохла, или эти 500 если не сдохла - берешь из них 250, даешь второй мыши (первая если выжила, она заслужила свободу), далее 125, 65, 33, 18, 9, 5, 4, 2. тебе даже с лихвой хватит мышей, ну а так 9 дней по времени. а еще можно это делать на бомжах.
>>141667478Клята бiндеровка! Съeбi отседова!
>>141664528Нихуя не понял. Объясните проще, пожалуйста.
>>141662634 (OP)Это говно мамонта уже давно все обсосали, тащи что нибудь новее
>>141664440И почему оно будет номером отравленной бутылки? Я нихуя не понял
>>141664610Годно кстати, самый адекватный метод
>>141668104Как поменять местами инт переменные, не используя буфер?Почему Вас нет ВКонтакте? Вы от кого-то скрываетесь?Вы женаты? А почему?
>>141665208Да ладно, в чгк на такое невозможно ответить, если заранее не знать
>>141667989Двоичнй код знаешь? 0=0000000000, 125=001111101 итд. http://www.calculator.net/binary-calculator.html?d2bnumber1=125&calctype=d2b&x=55&y=14Для каждого числа можно сделать последовательность нулей и единиц, по которой это число однозначно определяется. Если число меньше 1024, в последовательности будет не более 10 нулей/единиц. Далее по плану.
>>141668398>>141668193
>>141668398Спасибо, мудрый анон
