Get that job at Google - очень популярный пост с советами по поводу того как проходить собеседование в Гугле. И он не зря такой популярный, он действительно очень хорошо и вдумчиво написан. Там рассматривается процесс собеседования в принципе и даются советы, которые подойдут для прохождения собеседования в любых программерских компаниях.
Один вопрос там остался за кадром. Сейчас модно давать на интервью логические задачки. Не только для того, чтобы проверить логическое мышление, а потому что это пользуется популярностью у кандидатов. Nerd sniping такой :-).
Поэтому я решила к этому посту прицепить бонус. Итак, внимание, логическая задачка. Мне её когда-то давно прислал Sergey_.
Патриций решил устроить праздник и для этого приготовил 240 бочек вина. Однако к нему пробрался недоброжелатель, который подсыпал яд в одну из бочек. Недоброжелателя тут же поймали, дальнейшая его судьба неизвестна.
Про яд известно, что человек, его выпивший, умирает в течение 24 часов. До праздника осталось два дня, то есть 48 часов. У патриция есть пять рабов, которыми он готов пожертвовать, чтобы узнать в какой именно бочке яд. Расскажите каким образом можно это узнать.
Updated 23.04.2008 Судя по комментариям, многие подумали, что это задачка с Гугловского собеседования. Нет, мне ее прислали по Аське. Это просто интересная задачка.
Updated 20.07.2008
Первым правильный, а, главное, очень подробно расписанный ответ дал GT rocker. Также в комментариях приведена куча неправильных решений, с объяснениями почему именно они неправильные. Почитайте всё это, прежде чем писать в комментарии своё решение :-)
Left DataDog
3 дня назад
Atom feed
107 коммент.:
В течение 24 часов... значит ли это, что он и через 10 минут может умереть?
По моему, эта задачка очень схожа с той, которой сталкивался при собеседовании в другой очень известной копмании :)
Есть 3 упаковки с таблетками, одна упаковка с бракованными таблетками а две нет. Известно, что вес одной бракованной 1г,а бракованной 1.01г. В нашем распоряжении есть электронные весы (те которые с одной чашей) и у нас есть возможность воспользоваться весами один раз (только одно взвешивание!). И так вопрос - как за одно взвешиваени определить, в каком тюбике таблетки бракованные ? :)
описался - вес небракованной 1г а бракованной 1.01г
Стандартный способ: пять рабов начинают бить недоброжелателя и продолжают, пока он не скажет :)
240 бочек на 5 рабов означает, что каждому из них достанется по 48 бочек для проверки. Hаливаем рабам каждые пол часа из разных бочек. Kогда один из них умрет, проверим из какой бочки он пил 24 часа назад. Eсли смерть может наступить за меньший срок, тогда Ой. =)
Нужно для каждого раба разбить бочки на три части так, что бы в каждую часть для одного раба входило по одной трети частей любого другого раба. Такое разбиание оставим на как домашнее задание :) . Дальше каждый раб пробует вино из каждой бочки какой-то одной своей части. Если он умер - то число бочек в которых нужно искать сокращается в 3 раза (т.е умножается на 3), а если не умер - то умножается на 2/3 . Таким ообразом через сутки у нас есть 240 * (2^n) / (3^5) = 240 / 243 * (2^n) = чуть меньше чем 2^n подозрительных бочек, где n - число выживших рабов. А через сутки устраиваем такую же лотерею, но только теперь для каждого раба делим оставшиеся бочки по-честному на 2 части.
Поправка, не умножается на 3, а умножается на 1/3
На самом деле в таком варианте задача неправильно сформулирована. "Пожертвовать пятью рабами не нужно". Все равно умрет только один.
Т.е. берем 240 рабов - а в условии не сказано что у хозяина нет 240 рабов, только что пожертвовать можно только пятью. Наливаем и ... оппа. Один раб мертв и мы сэкономили четверых ))
Но в условии так же не сказано, что у хозяина есть 240 рабов.
2Olga:
В течение 24 часов... значит ли это, что он и через 10 минут может умереть?
Да
2Алексей:
Eсли смерть может наступить за меньший срок, тогда Ой. =)
Ой :-)
2Mikhail Elashkin:
а в условии не сказано что у хозяина нет 240 рабов
Какие-то нечестные приемы пошли :-).
ОК, добавим. "У хозяина нет 240 рабов".
2Анонимный:
пять рабов начинают бить недоброжелателя и продолжают, пока он не скажет :)
Это называется "творческий подход". :-)
у меня почему-то выходит, что при сохранении остальных условий можно даже из 251-ой бочки определить отравленную. я прав или как?
2mako:
Есть 3 упаковки с таблетками, одна упаковка с бракованными таблетками а две нет...
Я бы вытащила из первой упаковки одну таблетку, из второй две, из третей три и посмотрела бы на вес.
Вроде получается, что в совокупности есть 10 попыток и каждый раб может хоть 240 сразу попробовать.
240 < 2^8 следовательно должно хватить.
Осталось порубить бочки на порции правильные. По 48 на рыло -- один отвалился, стало быть партию нашли.
Следующий тур по 48/4 -- по 12 на рыло.
Вероятность есть, конечно, что мучиться до конца будут, а если раньше откинутся, то еще пару туров можно провернуть.
Так что как повезет, минимум жертвуем 2 рабами и 12 бочками, а максимум всеми рабами.
В общем, к моменту "догоняться" они все должны сыграть в ящик гарантированно ))
2tantv:
Такое разбиание оставим на как домашнее задание :)
Не, так не пойдет. Отвечать так уж целиком. И вообще ответ какой-то мутный...
2GT rocker:
у меня почему-то выходит, что при сохранении остальных условий можно даже из 251-ой бочки определить отравленную. я прав или как?
Затрудняюсь ответить. Лично я не знаю как проверить 251 бочку...
все очень просто, почему два дня? потому что за один день нужно пробовать 120 бочек. Какая связть между числами 120 и 5? Совершенно верно 120 это число перестановок числа 5.
у меня получилось с точностью до 4х бочек))
1й день, бочки разбиваем на группы по 24, каждый раб пробует из 2х разных групп (всего он попробует из 48 бочек). На тот свет отправятся 2 счастливых раба =)
На следующий день делим 24 бочки, из которых пили оба умерших раба, на группы по 4, опять каждый раб пробует из 2х бочек, опять умирают двое, в результате мы вычисляем с точностью до 4х бочек.
В общем здесь нужно максимизировать количество отравленных рабов))
у нас есть 2 раза по 24 часа, то есть 2 шага.
начнем с последнего.
надо определить, из скольки бочек мы сможем выбрать отравленную, если у нас осталось 5, 4, 3, 2, 1 или 0 рабов после первого шага.
если 0, то мы ничего не можем определить.
если 1, то из двух.
2 - 4
3 - 8
4 - 16
5 - 32. здесь все понятно.
теперь можно перейти к первому шагу.
1. нельзя, чтобы умерли все рабы, и осталась неопределенность. поэтому, все рабы вместе должны попробовать только одну бочку. итак, +1.
2. четыре раба имеют право умереть, оставив неопределенность в 2 бочки. поэтому из двух бочек могут пробовать по четыре раба. 2 умножаем на размещение из 5 по 4 и получаем 10. из десяти бочек могут пить четыре раба одновременно. +10.
3. аналогично для смерти трех рабов - 4 * С(из 5 по 3) = 4 * 10. +40.
4. для смерти двух - 8 * С(из 5 по 2) = 8 * 10. + 80.
5. для смерти одного - 16 * С(из 5 по 5) = 16 * 5. +80.
6. никто не должен пить из 32 бочек. +32.
таким образом, по комбинации умерших на первом шаге мы определим 32, 16, 8, 4 или 2 бочки, в которых есть яд. число выживших позволит нам на втором шаге определить одну-единственную отравленную бочку.
а вот с суммой я ошибся в предыдущем посте.
1 + 10 + 40 + 80 + 80 + 32 = 243.
итак, можно одну отравленную бочку определить из 243-х.
P.S. могу ошибаться :)
2johndegree:
а если в первый день кто-то умрет, то как ты свяжешь число оставшихся и 120?
в 39-й бочке яд
Вот про таблетки хорошая задачка, а задача с бочками на практике не решается, ибо не учитывается разбавление яда в N раз - он может и не подействовать уже.
Опять таки условие из пальца высосано - 240 бочек вина значит есть, а 240 рабов нет - ну не фигня ли? :)
Вообще большая часть этих алгоритмических задач не имеет физического(реального) смысла, так как носят умозрительный характер (задача ради задачи).
Возмём к примеру "простенькую" задачу про шнуры:
"Есть два разных бикфордовых шнура, каждый из которых сгорает ровно за час. У этих шнуров есть одно свойство: сгорают они неравномерно (то есть половина шнура необязательно сгорает за 30 минут).
Как при помощи этих шнуров и зажигалки отмерить 45 минут?"
Ну каким извините способом вы намереваетесь изготовить бикфордов шнур сгорающий ровно за час из неравномерно горящего материала? о_0
Если смерть может наступить быстрее 24 часов, то надо подумать.
Хотя идея решения думаю, ясна уж сейчас:
нужно сгруппировать бочки по парам, тройка... затем из бочек каждой группы рабы пьют вино, из какой-то - все (видимо, в этой группе - 1 бочка), из какой-то не все.
После первых 24 часов, у нас либо не остается работв вовсе. значит отравлена та самая группа из одной бочки, из которой все пили, либо 1..2... и т.д. рабов и известна группа из 2 и т.д. бочек, среди которых одна отравлена. Далее оставшимися рабами находим какая из бочек группы отравлена.
Над точным решением, над тем как группировать нужно подумать.
2GT rocker: блин ну просто же все:
бочка 1 - пробует раб 1
бочка 2 - пробует раб 2
...
бочка 6 - пробуют рабы 1 и 2
...
бочка 120 - пробуют рабы 1,2,3,4 и 5
если яд в 1-й бочке то умрет раб 1, если в 120-й то умрут все пятеро. Мы изобрели 5-ти ричную систему счисления :)
Выше оказывается уже написали решение :)
Главное чего я не мог понять - начального условия: кандидат _очень_ хочет в google ;-)
Про таблетки:
Взвешиваем сразу упаковками, либо, если можно, вытаскиваем по таблетке из каждой упаковки. Если одна из взвешиваемых тяжелее, то она бракованная. Если вес взвешиваемых равен, то бракованные таблетки в той упаковке, которую не взвешивали. Так?
2GT rocker:
итак, можно одну отравленную бочку определить из 243-х.
P.S. могу ошибаться :)
Всё правильно.
2Tardos Mors:
Если одна из взвешиваемых тяжелее, то она бракованная.
Там в условии весы электронные, с одной чашей.
Число 240 быстро "выдаёт", где зерглин закопан. Потому что 243 - это 3^5, а рабов как раз 5, и состояний у каждого может быть 3.
Патрицию нужно устроить рабам 2 соревнования по литрболу - первое в момент T0 = 0, второе - в момент T1 = 24 часа. К моменту начала праздника (T2 = 48 часов) каждый из рабов будет находиться в одном из трёх состояний: умерший в промежутке [T0,T1) - состояние "0"; умерший в промежутке [T1,T2) - состояние "1"; живой после обоих раундов (зависит и от вина, конечно, если концентрация яда такова, что для его детектирования нужно выпить целый бокал, то выжить после 80-ти бокалов, выпитых в единовременно в первом раунде может быть проблематично, независимо от наличия там яда - но к логике задачи это не относится) - состояние "2".
Добавим три "виртуальные" (пустые) бочки и запишем номера бочек в троичной системе, отсчитывая сами бочки с нуля:
00000 - 0
00001 - 1
00002 - 2
00010 - 3
...
22210 - 237
22211 - 238
22212 - 239
22220 - 240 (пустая)
22221 - 241 (пустая)
22222 - 242 (пустая)
Троичные значения соответствуют состояниям рабов к моменту T2 (три последних состояния невозможны, поскольку пустая бочка не является отравленной). Патрицию остаётся лишь собрать эту информацию и определить по ней отравленную бочку. Для того, чтобы троичное значение номера бочки соответствовало кортежу состояний рабов, нужно выдавать им вино следующим образом:
в первом раунде каждый раб пьёт из тех бочек, у которых в троичном номере стоит "0" в разряде, соответствующем номеру раба; во втором раунде - пьёт из тех бочек, где в его разряде стоит "1". Если в данном разряде стоит "2", то раб не пьёт из этой бочки вообще. Примеры: из бочки номер 3 (00010) в первом ранде пьют все рабы, кроме 4-го, который пьёт из неё во втором раунде; из бочки номер 239 (22212) не пьёт никто, кроме 4-го, который пьёт из неё во втором раунде.
Если кто-то из рабов умирает до начала второго раунда, то число подозрительных бочек сокращается до 3^k, где k - число выживших рабов. Подозрительными остаются бочки, в номерах которых были нули в разрядах, соответствующих умершим рабам.
В итоге к началу праздника будет получен кортеж состояний рабов, который представляет собой троичный номер искомой бочки.
2 Алёна:
Разбить можно так: имеем n от 1 до 5 - номера рабов и k от 1 до 240 - номера бочек. Для каждого раба и бочки высисляем m = (k*(3^n))%240. В первую треть входят бочки с m < 80, во вторую с 80 <= m < 160 и в третью с 160 <= m
2altera:
круто!
2johndegree:
2GT rocker: блин ну просто же все:
бочка 1 - пробует раб 1
бочка 2 - пробует раб 2
...
бочка 6 - пробуют рабы 1 и 2
...
бочка 120 - пробуют рабы 1,2,3,4 и 5
если яд в 1-й бочке то умрет раб 1, если в 120-й то умрут все пятеро. Мы изобрели 5-ти ричную систему счисления :)
Если ты распишешь те места, что забил точками, то увидишь, что у тебя в сумме 120 не получится.
Очевидно, что пятью рабами, которые имеют только 2 состояния (жив, мертв) за один раз можно определить только 32 бочки. К счастью у нас две попытки.
Делим все бочки на неравные группы. 5 групп по 16 бочек, кодируем их 00001, 00010, 00100, и т.д. 9 групп по 8 бочек (00011, 00101,...). 9 групп по 4 бочки (00111,...), 5 групп по 2 бочки (01111,...), 1 группа из 32 бочек (00000). Рабы пьют все бочки в группах, в кодах которых взведены их биты. Умершие рабы однозначно определяют код группы. Ну со вторым подходом, думаю, уже все понятно.
По-моему, число бочек в условии можно увеличить до 241, нет? Если добавить еще одну бочку из которой будут пить все рабы в первый раз.
2orionics:
По-моему, число бочек в условии можно увеличить до 241, нет?
До 243.
GT rocker расписал выше почему.
Да, действительно:
1 + 10 + 40 + 80 + 80 + 32 = 243.
С числами напутал.
2Алёна
правильное решение предложила, хотя там можно и разные количества таблеток из разных пачек брать, всё равно ошибиться будет невозможно :)
Будь у патриция 6 дней, можно было бы обойтись всего 3-мя рабами...
А как задачка с бикфордовыми шнурами решается?
По-моему, там нужно один поджечь с двух сторон. Когда догорит - получим 30 минут. И тут же складываем пополам второй и тоже поджигам с двух сторон - будет 15 минут.
Можно количество бочек до 244 увеличить - за счёт "предварительно отложенной" бочки. То есть если ни в одном из раундов никто не траванулся - значит отложенная бочка с ядом.
делим бочки на колличество рабов - каждому по 48. бочки каждого раба делим на 5 ~ 10.
тоесть каждый раб пробует из своих 48 + из 9-10 другого раба. тогда через 24 часа умрет 1 или 2 раба (в худшем случае) и у нас останеться 9-10 подозрительных бочек и 4-3 раба. повторяем предыдущие шаги и выходим на подозрительную бочку :)
2win32asm:
Можно количество бочек до 244 увеличить - за счёт "предварительно отложенной" бочки.
Она уже входит в 243.
Artem
делим бочки на колличество рабов - каждому по 48. бочки каждого раба делим на 5 ~ 10.
тоесть каждый раб пробует из своих 48 + из 9-10 другого раба. тогда через 24 часа умрет 1 или 2 раба (в худшем случае) и у нас останеться 9-10 подозрительных бочек и 4-3 раба.
У нас останется 20 подозрительных бочек (берем худший случай) и 3 раба. Потому что раб A пробует из доли раба B, но и раб B пробует из доли раба A.
Допустим яд идеален и смерть наступает ровно через 24 часа.
В течении первых 24 часов поим каждые полчаса рабов из новых бочек, отмечаем в табличке кто и во сколько откуда пил. За 24 часа мы уже все бочки опробовали и следующие 24 часа наблюдаем за пьянющими рабами. Когда один раб умерает, то смотрим на время, смещаем на 24 часа и по табличке смотрим откуда он в это время пил. Одна жертва, его поминают, и приступают к пьянке. Остальные 4 раба пережив шок ещё больше напиваются и вызывают Иисуса дабы тот ещё больше преумножил вино :)
Решение для 243 бочек описано выше.
Вроде можно решить задачу для 243+32=275 бочек. А больше можно?
2Znah:
Решение для 243 бочек описано выше.
Вроде можно решить задачу для 243+32=275 бочек.
Хм. Как?
2RedChrom:
Допустим яд идеален и смерть наступает ровно через 24 часа.
Тогда это будет уже другая задача :-)
В самом начале делим бочки в группы по 48. К каждой группе по рабу.
В 1ом заходе каждый раб выпивает все из своей группы + по 12 из 4х оставшихся групп. Причем каждый раб пьет те 12 бочек, из которых не пробывали 3 других.
После первого раунда обязательно умрут 2 раба, таким образом мы определим 12 бочек.
Делим на группы по 3, каждый раб, аналогично предыдущему, пьет из своей группы + по 1му заходу их других групп. Дополнительные заходы опять же - не повторяются.
Умрут 2 раба оставив нам ровно 1 ядовитую бочку.
Например:
Заранее предположим что яд в 1ой группе(для остальных будет аналогично)
12 12 12 12
умер, допустим 2ой раб, значит яд во 2ой подгруппе. Получим:
3 3 3 3
Опять же, предположим что яд в 1ой группе, тк для остальных все будет аналогично.
1 1 1
Допустим умер 3ий раб, значит яд был в 3ей бочек в группе.
Скольких профессионалов недосчитается теперь Гугол...
2Алёна:
Никак, я ошибся :)
Алёна, вся наша фирма тебя обожает.
Мы ходим задумчивые и улыбаемся, как влюблённая десьтиклассница.
1) На поиски дано только 48 часов, а яд действует в течение 24. Следовательно, поиски должны завершится максимум в два этапа (разлили, чокнулись, выждали сутки, посчитали выживших и снова разлили, выждали, посчитали).
2) Один раб годится на проверку двух бочек - пьет из одной бочки – если умер, значит, в ней был яд, если же нет – яд в другой бочке. Т.е. один раб – это один бит информации. Соответственно, двумя рабами можно проверить четыре бочки: из первой бочки никто не пьет (00), из второй бочки пьет первый (01), из третьей – второй (10), из четвертой – оба (11). Ну и так далее: три раба – восемь бочек, четыре – шестнадцать, а все пять, соответственно – 32. Норма :)
Из п.2 напрямую следует, что чем больше рабов погибнет на первом этапе, тем больше информации это должно нам дать, сильнее сузить круг поисков. Т.е. надо сделать так, чтобы потеря только одного раба сужала круг подозреваемых до 16 бочек, двух – до 8, трех – до42, четырех – до 2.
Делим бочки на группы:
Группа A1, 32 бочки – из них никто не пьет.
Группы B1 – B5 по 16 бочек – из каждой группы пьет только один раб. Например, из А1 – раб N1, из A2 – раб N2 и т.д.
Группы С1-С10 по 8 бочек. Из каждой группы пьют по два раба. Всего возможно 10 способов набрать по два элемента из пяти (12, 13, 14, 15, 23, 24, 25, 34, 35, 45), поэтому получится десять групп.
Группы D1-D10 по 4 бочки. Из каждой группы пьют по три раба. Всего возможно 10 способов набрать по три элемента из пяти (123, 124, 125, 134, 135, 145, 234, 235, 245, 345), поэтому получится десять групп.
Группы E1-E5 по 2 бочки. Из каждой группы пьют по четыре раба. Всего возможно 5 способов набрать по четыре элемента из пяти (2345, 1345, 1245, 1234), поэтому получится пять групп.
Итого: 32 + 5*16 + 10*8 +10*4 + 5*2 = 242 бочки, баста.
Выпили, выждали сутки. Смотрим, кто уже не с нами. По номерам погибших определяем группу с отравленной бочкой. Дальше, в общем, все просто – как сказано в следствии из п.2, чем меньше осталось в живых, тем меньше будет группа подозрительный бочек.
Если выжили все 5 рабов, то надо проверить группу A1, 32 бочки. Строим их по росту, самый низкий будет младший бит :) И снова наливаем:
Нулевая бочка – 00000, никто не пьет.
Первая бочка – 00001, пьет N1
Вторая бочка – 00010, пьет N2
Третья бочка – 00011, пьют N1 и N2
…
Двадцать девятая бочка – 11101, пьют все кроме N2
Тридцатая бочка – 11110, пьют все кроме N1
Тридцать первая бочка – 11111, пьют вообще все.
Ждем вторые 24 часа, по отравившимся битам находим бочку. Если все живы, то отравлена нулевая бочка.
Если выжили четыре раба, то надо проверить какую-то из групп B, 16 бочек, идея та с битами же. И т.д. для трех, двух и одного раба.
---
За сколько минут надо было решить, чтобы взяли?
2Kulakov:
После первого раунда обязательно умрут 2 раба, таким образом мы определим 12 бочек.
Аналогичное решение уже предлагали выше. Не получится там 12 бочек, больше будет, потому что раб A пробует из доли раба B, но и раб B пробует из доли раба A.
2Анонимный:
Алёна, вся наша фирма тебя обожает.
Вау, спасибо, привет фирме :-)
2atwain:
За сколько минут надо было решить, чтобы взяли?
Я не знаю, мне ж ее просто по Аське Серега скинул.
На самом деле в таких задачах на интервью проверяется не столько способность решить задачу, сколько последовательнось действий, способность логически мыслить. И еще это самореклама. Ведь ты, придя домой расскажешь про эту интересную задачу другим гикам.
Перемешать все бочки - концентрация яда будет ничтожной - никто не умрет.
2Алёна
Она уже входит в 243.
Хм.
первый заход:
на всех пятерых 1 бочку
каждой четвёрке (5) по 2 бочки
каждой тройке (10) по 4 бочки
каждой паре (10) по 8 бочек
каждому (5) по 16 бочек на нос
(ещё 32 бочки отложим на второй раунд и одна моя 8-) )
исходы 1 раунда:
если кто-то потравился - очевидно. выделяем группу бочек, травим оставшихся. моя бочка не отравлена.
если никто не отравился - спаиваем всем 5-рым 32 отложенные бочки, статус моей бочки пока не определён
исходы 2 раунда:
если в первый заход кто-то траванулся, кто-то траванётся и во втором. моя бочка чиста.
если в первый никто не траванулся, но траванулись во втором раунде - опять же моя бочка чиста
а вот если никто не траванулся и во втором раунде - тогда моя бочка с ядом.
считаем:
(1 раунд)
1 + 2*5 + 4*10 + 8*10 + 5*16 +
(2 раунд)
32 +
(моя бочка)
1 = 244.
Извините за занудство. 8-)
Задачку с таблетками можно решить так: на весы кладем одну таблетку из первой упаковки, две из второй и взвешиваем.
Если в результате имеем 3 грамма, то бракованные таблетки - в третьей упаковке.
Если в результате имеем 3.01, то брак в первой впаковке.
Если 3.02 - то во второй.
2win32asm: Последние 32 бочки уже включают благополучный исход (никто не отравился). Из одной из бочек никогда не пьют.
http://www.interwave.ru/forum/archive/index.php/t-21033.html
?
Разделить бочки на 5 групп. Каждому рабу получится по 48. На первом этапе каждый выпивает из своих бочек и пробует по 9 бочек из других групп, причем первый раб пробует 9 первых, второй 9 начиная с 10-ой и т.д. В каждой группе остается по 3 бочки не попробованной 2-мя рабами (самый простой вариант - яд в одной из них, тогда на втором этапе остаются 4 раба и 3 бочки). На втором этапе остаются 9 бочек и 3 раба (худший случай). Опять все делиться на 3, каждый пробует свою групп и одну из чужой, со смещением.
Привет Алена, спасибо тебе за твой блог :-)
Решение первое (простое, с наименьшим кол-вом жертв и условием что яд действует ровно через 24 часа). Каждый раб пробует по одной пронумерованных бочек каждые полчаса. Т.е. за 24 часа он проверяет 48 бочки и 240 бочек 5 рабами. Дале засекается время и все ожидают когда один из несчастилвчиков покинет этот мир, время в которое это произойдет нужно умножить на 2 что бы узнать номер бочки.
Вариант второй (умирают двое, выпито тоже больше) Все бочки делят на 10 групп по 24 в каждой. Первый раб пьёт из 1,2,3,4 группы, второй из 1,5,6,7, третий из 2,5,8,10, четвертый из 3,6,8,9, пятый из 4,7,9,10 и так каждый час по одной бочке из каждой группы. Таким образом двое пьют из одной бочки. После этой попойки (после 24 часов), время сметри (номер часа) обоих несчастных будет указывать на номер бочки из соответствующей группы.
Борис
2Abu:
http://www.interwave.ru/forum/archive/index.php/t-21033.html
?
А в чем вопрос?
2sash_ko:
Разделить бочки на 5 групп. Каждому рабу получится по 48. На первом этапе каждый выпивает из своих бочек и пробует по 9 бочек из других групп
Этот варинат уже предлагали, не будет он работать. Я выше объясняла почему.
2Борис:
Привет Алена, спасибо тебе за твой блог :-)
Пожалуйста! :-)
После этой попойки (после 24 часов), время сметри (номер часа) обоих несчастных будет указывать на номер бочки из соответствующей группы.
Решение через биномиальные коэффиценты надежнее, может яд действует на всех по-разному...
Но вообще интересная мысль, такого еще не было.
2Вадим
> А как задачка с бикфордовыми шнурами решается?
Поджигаем с обоих сторон первый шнур, и с одной стороны - второй.
Когда первый шнур полностью сгорит, поджигаем второй еще и с другого края. Когда он догорит до конца, это и будет 45 минут с момента начала.
Это верный ответ или нет:
=
1 раб может распознать за раз яд в одной из двух бочек(или умрёт, или нет)
2 раба могут распознать за раз яд в 4х бочках (или оба умрут, или 1, или
2, или никто - итого, 4 бочки)
3 раба могут распознать яд в 8 бочках (8 комбинаций)
4 раба - 16 бочек
5 рабов - 32 бочки могут проверить за раз
Итак, первая пьянка:
Одну бочку пробуют все. Если помрут - значит она.
Затем берётся 10 бочек. Каждый пьёт из 8 так, чтоб из каждой бочки
выпили только 4 раба. Если яд в них - выживет ровно 1. Он и определит, в
какой из двух бочек, из которых не пил, находиться яд(во вторую пьянку)
Затем берётся 40 бочек. 5 рабов можно организовать по 3 раба десятью
комбинациями. Каждая тройка рабов пьёт из определённых 4 бочек. Если яд
будет в одной из этих 40 бочек, тройка умрёт, а оставшиеся 2 раба
проверёт доставшиеся им 4 бочки.
Затем берётся 80 бочек. 5 рабов можно разбить на пары опять же десятью
способами. Если какая-то пара померла, то попробованные ей 8 бочек
проверит выжившая тройка.
Затем берётся 80 бочек. Каждый раб пьёт из 16ти. Если один умирает,
оставшиеся 4 определяют яд в 16ти бочках, опробованных ими.
Конец первой пьянки
И наконец на вторую попойку можно зарезервировать 32 бочки. Если рабы не
умрут, значит яд в этих 32х бочках. За один присест они их проверят.
Итак, общее число бочек - 1+10+40+80+80+32 = 243 бочки. Т.е. 5ю рабами
можно проверить 243 бочки за два этапа
=
?
Умный раб симулирует отравление и будет "мучиться" до конца опытов или до отравления гостей.
gt rocket, altera, молодцы!
получается что в общем виде
для N рабов за M суток могут проверить:
(M+1)^N бочек
PS. Кстати, случай когда можно проверять только один раз - это избыточный код имени кого-то для определения и восстановления убитого бита в посланном сообщении.
PPS. а если бы несколько бочек было отравлено то это уже код определения нескольких сбойных битов.
поэтому интересно, если бы было отравлено от 0 до К бочек включительно, то сколько бочек максимум можно было бы проверить и обезвредить с помощью N рабов за M дней?...
Есть способ сократить число подозрительных бочек до 8 в худшем случае.
Делим бочки на группы (на 6 групп), даем отпить по кубку/глотку из каждой бочки. Если раб умер - дели эту группу еще на 5 и даем отпить оставшимся 4-м рабам на следующий день. Соответственно, если ни один через сутки не помрет, то яд в оставшейся группе, которую не пробовали на обеих итерациях.
В лучшем случае нам придется выкидывать 7 бочек, 6.(6) точнее.
15+15*15 by hodzanassredin
2Abu:
Это верный ответ или нет:
верный
Мда... Для меня слишком сложно.
Ivan S. Lyapunov
Перемешать все бочки - концентрация яда будет ничтожной - никто не умрет.
Браво!
Вот так вот решают задачи настоящие инженеры - быстро и эффективно :)
Даешь больше бочек. 260?
Делим бочки на 26 груп.
(x11 x12 x13 x14 x15
x21 x22 x23 x24 x25
x31 x32 x33 x34 x35
x41 x42 x43 x44 x45
x51 x52 x53 x54 x55)
и еще одна группа группа x0.
В каждой группе по 10 бочек.
Каждый i негр пьет i ряд и j столбец. В итоге умирают, либо 1, либо 2, либо 0 негров(яд в x0). => имеем как минимум 3 негра и одну группу из 10 бочек. Далее аналогично. Матрица 3x3 + запасная бочка. Теоретически даже есть шанс неграм остаться в живых.
Виноват i-й ряд и i-й столбец.
А вообще Ivan S. Lyapunov рулит.
"Перемешать все бочки - концентрация яда будет ничтожной - никто не умрет."
А если негры подойдут с чувством к делу, то пьянка получится грандиозная.
2Анонимный:
и одну группу из 10 бочек
Две группы по 10 бочек на самом деле.
Ура, три дня решала, если честно...
Разжевываю как для "нематематиков"
И вот оно:
Посчитаем комбинации 5 умерших рабов – 32 проверенные бочки
5 рабов (1,2,3,4,5) – 1 бочка
4 раба (1234, 1235, 2345, 1345, 1245) – 5 бочек
3 раба (123, 124, 125, 134, 135, 145, 234, 235, 245, 345) – 10 бочек
2 раба (12, 13, 14, 15, 23, 24, 25, 34, 35, 45) – 10 бочек
1 раб – 5 бочек
1 бочку отставляем – если она – то все живы.
Посчитаем комбинации 4 умерших рабов – 16 проверенных бочек
4 раба (1234) – 1 бочка
3 раба (123, 124, 134, 234) – 4 бочки
2 раба (12, 13, 14, 23, 24, 34) – 6 бочек
1 раб – 4 бочки
1 бочку отставляем – если она – то все живы.
Посчитаем комбинации 3 умерших рабов – 8 проверенных бочек
3 раба (123) – 1 бочка
2 раба (12, 13, 23) – 3 бочки
1 раб – 3 бочки
1 бочку отставляем – если она – то все живы.
Посчитаем комбинации 2 умерших рабов – 4 проверенных бочки
2 раба (12) – 1 бочка
1 раб – 2 бочки
1 бочку отставляем – если она – то все живы.
Получается на День 2:
1 оставшийся на след день раб может проверить 2 бутылки, 2 раба – 4 бутылки, 3 раба – 8 бутылок, 4 раба – 16 бутылок, 5 рабов – 32 бутылки.
Поэтому максимум мы можем оставить на след день 32 бутылки при всех живых рабах.
День 1:
32 никто не пробует, т.к. если среди этих 32 отравленная бутылка – то мы сможем ее найти на 2 день с помощью 5 живых рабов.
Значит 1 бочку пьют все 5 рабов сразу все вместе, если все 5 умрут – значит она отравлена.
Предположим 1 раб должен выжить – 4 умерли, тогда мы можем смешать по 2 бочки, т.к. 1 выживший раб на 2 день нам определит 1 из 2 бочек. Значит мы можем потерять 4 раба в 1 день, а из 4 рабов у нас можно составить 5 комбинаций. Значит берем 10 бочек и смешиваем по 2 – получаем 5 смесей – как раз столько же и комбинаций.
Предположим 2 раба должны выжить – 3 умерли, тогда мы можем смешать по 4 бочки (потому что 2 раба на 2 день смогут проверить именно 4 бочки. Не больше)
Из 3-х умерших рабов у нас может получиться 10 комбинаций, поэтому смешиваем 40 бочек, в каждой по 4 бочки – получается 10 смесей.
Предположим 3 раба должны выжить – 2 умерли, тогда мы можем смешать по 8 бочек (потому что 3 раба на 2 день смогут проверить именно 8 бочек. Не больше). Из 2-х умерших рабов у нас может получиться 10 комбинаций, поэтому смешиваем 80 бочек, в каждой по 8 бочек – получается 10 смесей.
Предположим 4 раба должны выжить – 1 умер, тогда мы можем смешать по 16 бочек (потому что 4 раба на 2 день смогут проверить именно 16 бочек. Не больше). Т.к. мы можем потерять только 1 раба, то делаем 5 смесей (по 1 смеси для каждого) из 16 бочек.
Суммируем проверенные бочки:
1 (если умерли все 5)
80 (16*5 - если выжили 4)
80 (8*10 - если выжили 3)
40 (4*10 - если выжили 2)
10 (2*5 - если выжил 1)
32 остается – их никто не пробует
Всего 243, что происходить в день 2 см.выше
2анонимный
>Возмём к примеру "простенькую" задачу про шнуры:
...
Ну каким извините способом вы намереваетесь изготовить бикфордов шнур сгорающий ровно за час из неравномерно горящего материала? о_0
Очень просто, если у меня есть два одинаковых шнура из неравномерно горящего материала и часы. Поджигаю первый шнур, засекаю время, через час отрезаю от второго шнура кусок, равный по длине сгоревшей части второго шнура.
Как можно изготовить два шнура с одинаковым значением скорости горения в каждой точке. Сделать шнур можно из трубки, в которую засыпать порошок. Непрерывно варьируя качество порошка (быть может добавляя негорючий материал) можно добиться любого распределения скоростей горения по трубке.
Да… задачка доставила удовольствие.
Первая мысль – 5 рабов за один заход могут дать 32 комбинации. Но нужно оставить несколько рабов на второй заход.
Выберем те комбинации из 32, при которых остаётся некоторое количество рабов на другой ход.
Предположим, два идут на первый (С2/5 = С3/5 = 10, больше брать смысла не имеет), три на последний.
Тогда за первый заход можем проверить десять групп бочек, остаётся 24 на трёх человек. Много.
Так! Но можно же брать не только комбинации, в которых два бита равны единице.
Можно брать те, в которых число единиц меньше либо равно двум. Это 16 из 32.
240/16 = 15. Такой мизер тремя рабами не ловится… Скверно.
Мысль: в некоторых случаях на второй ход остаётся больше трёх рабов. Нельзя ли использовать это преймущество?
Мы можем проверить 16 групп бочек, используя те пятибитовые комбинации, в которых не более трёх единиц.
! Но не обязательно количество бочек в этих группах должно быть одинаковым.
Для комбинаций, после которых остаётся больше рабов, можно использовать группу с бОльшим количеством точек.
Будем учитывать то количество
бочек, которое мы сможем исследовать остатком рабов.
Если после первого эксперимента у нас остаётся 5 рабов, мы можем исследовать с помощью них 32 бочки. Если 4 – 16 бочек. Если 3 – 8 бочек.
Комбинаций с нулём единиц у нас одна, с одной – 5, с двумя – 10.
Выделяем группу бочек числом 32 (из которых никто не будет пить), под 00000, пять групп бочек числом 16 для одноединичных комбинаций и 10 груп числом 8 под двухъединичные комбинации.
1*32 + 5*16 + 10*8 = 192. Мало. Но близко.
Блин, а кто сказал, что за первый заход мы можем сгнобить только двух рабов?
Если мы сгнобим трёх, после этого мы сможем исследовать 4 бочки (но комбинаций из трёх рабов 10, на каждую мы можем выделить по 4 бочки), если у нас останется один раб – с его помощью можно будет проверить две бочки. Ну а если все умрут – на это событие 11111 можно поставить группу в одну бочку.
Продолжим ряд:
1*32 + 5*16 + 10*8 + 10*4 + 5*2 + 1 = 243.
Похоже, в общем случае (N рабов и k дней) рекуррентная формула будет такой:
M(k, N) = Sum(i = 0, N) { C(i,N) * M(k-1, N-i) }
M(1, N) = 2^N
простое решение:
делим 240 бочек на 6 групп по 40 бочек, 1 раб распробует вино из всех бочек первой группы, 2 - из второй и тд. Если через 24 рабы остались живы - отравленная бочка в 6 группе, иначе имеем 4 раба и группу из 40 бочек.
далее делим 40 бочек на 5 групп по 8 бочек и 4 раба дегустируют вино каждый в своей группе. Через 24 часа либо они остаются живы и отравленая бочка находится в 5 группе, либо в той группе - которую дегустировал умерший раб.
таким образом получаем 240-8 НЕотравлееных бочек, которых оправляются на пьянку, а так как у нас осталось 3(в худшем случае) раба - они будут определять в какой бочке отравленное вино:
8 делится на 4 группы по 2, 3 раба пробуют из трех групп - если через 24 часа все живы- отравленная в 4 группе. Теперь у нас две бочки - даем ее одному (из 2 выживших) рабу - если он выживает - отравлена другая бочка.
Уже не меньше 4 раз правильное решение писали. Хватит, пора закрывать тему. А то откровенные глупости люди писать начинают.
Или можно переформулировать условие: доказать, что задача решена оптимально, т.е. что нельзя вычислить отравленную бочку из более, чем 243.
Смущает то, что бочек 240, а не 243... Может автор задачи сам не знал правильного решения? Есть один неверный путь в рзмышлениях, который приводит нас к 240-ка. Может автор его и имел ввиду?
Хотя люди уже призывают закрыть тему.
Рискну предложить свое оригинальное решение,
кстати имеющее еще одно преимущество, оно позволяет
решить задачу за 28 часов.
Итак, разбиваем 240 бочек на 5 частей по 48 бочек
соответственно каждый из рабов пьет из своей части.
Через час (выбрано как минимальная временная разница)
каждая из 5 частей делиться на 4 по 12 бочек в каждой,
из которых пробуют вино все рабы, кроме того кто пил
из всех 48 бочек этой группы, далее каждую группу из 12 бочек
делим на 3 по 4 бочки, каждую из групп по 4 бочки на 2 группы
по 2 бочек. Все. Поскольку расписать здесь все разбиение трудно,
приведу разбиение только начиная с 1 группы по 48
промежуток между дегустациями 1 час (0 - никто не пробует)
+0ч - 111111111111111111111111111111111111111111111111
+1ч - 222222222222333333333333444444444444555555555555
+2ч - 333344445555222244445555222233335555222233334444
+3ч - 445533553344445522552244335522552233334422442233
+4ч - 050405030403050405020402050305020302040304020302
Максимальный промежуток между началом теста и последней смертью
24+число подходов(5)-1=28 часов
Замечу, что в отличии от других решений число бочек точно соответствует
числу рабов необходимых для решения. Также решение не зависит от конкретных
физиологических свойств реципиентов т.е. смерть может наступить в любой промежуток
времени от 0 до 24 часов.
2Alexey:
возможно множество случаев, когда все(!) рабы умрут. И тогда никак не определить, в какой бочке яд.
если конкретнее, то есть 120 шансов умереть всем. 120 - умереть четверым. как же найти отравленную бочку?
2rocker:
Да - действительно, в моем методе определяющим является последовательность смертей. Например, если первым умер раб 1 - значит отравленная бочка в первых 48. Если Последовательность смертей 1 2 3 4 - значит это бочка №1 если 1 2 3 4 5 - значит №2, 1 2 3 5 - бочка №3 итд.
Т.е. интервал от принятия яда до смерти может быть любой до 24 часов, но одинаковый у всех.
А вы ведь говорили аська пустая трата времени.... Ето я к добавлению от 23 апреля....
А вы ведь говорили аська пустая трата времени.... Ето я к добавлению от 23 апреля....
Одно дело несколько близких друзей, а совсем другое - непрерывный поток сознания от людей, которых я совсем не знаю..
Я бы немножко поменял решение с состояниями, чтобы не было путаницы.
0 - не умер
1 - умер после первого захода
2 - после второго
Тогда номер захода, когда нужно пить бочку, находится в соответствующем разряде числа. Тогда нет сопоставлений 0 - в первом разряде, 1 - во втором... Правда, мы можем считать с нуля :)
С таблетками аналогично. Берём одну таблетку из первой упаковки, две из второй, три из третьей. Число сотых в весе является номером бракованной упаковки.
Спасибо за задачку :)
P. S. За соседним столом на работе сидит к.т.н., так он сразу начал думать в правильном направлении :)
Случайно наткнулся на эту задачу.
Подумал (не заглядывая в ответы)
У меня получилось, что можно пятью рабами взять 288 бочек.
Второй тур, где нужно вычислить конкретную точку — «бинарный пробник» (рабы=разряды), для множеств размером
16 (тремя рабами), 32 (четыремя рабами), 64 (пятью рабами).
Первый тур — покрыть исходное множество бочек пересекающимся по рабам множеством распробованных бочек так, чтобы после первого тура было вычислено множество, которое можно оставшимся числом рабов обработать как указано выше.
Для этого делам следующее разбиение:
64 бочки не пьет никто.
Каждый раб пьет по 64 бочки,
причем 32 бочки у каждого раба свои, а 16 бочками раб «пересекается» с соседним (1 со вторым, второй с третьим, пятый с первым).
Таким образом покрывается множество размером 64+5*64-6*16=288.
Три возможных исхода:
1. Никто не умер — 5 рабов атакуют множество размером 64.
2. Один умер — 4 раба атакуют множество размером 32.
3. Двое умерло — 3 раба атакуют множество размером 16.
Так что у задачи есть потенциал для закручивания гаек (возможно ли еще больше бочек «распознать» — я не в курсе…).
Ну либо найдите у меня ошибку, время позднее, мог и ошибится.
Хм. Ошибся. Можно взять и 304 бочки.
64+5*64-5*16=304.
(включения/исключения — пересечений пять, а не шесть, как я подумал сдуру).
Нет, извините, я идиот. У меня «Сдвиг на разряд» (5 рабов-разрядов это 32 бочки). Соотвественно, при даже если перебирать все комбинации рабов, получится (биномиальный коэфф. C^k_n):
32+С^1_5*16+С^2_5*8+С^3_5*4+С^4_5*2+C^5*5*1=
32+5*16+10*8+10*4+6*2+1=245
Т.е. только пять лишних бочек, по отношению к условию, можно впихнуть.
Сорри за беспокойство.
2Stas Fomin:
Т.е. только пять лишних бочек, по отношению к условию, можно впихнуть.
На самом деле не пять, а три.
Вместо 6*2 должно быть 5*2.
Вместо 6*2 должно быть 5*2.
Да, позор, окончательно убедился, что устный счет не моя сильная сторона. Значит работа в гугле мне не светит.
Но задачу надо переформулировать, ибо непонятно, почему вино настолько ценно, что приближенное решение (пожертвовать 5% бочек) тут не катит.
Сорри за мусор в комментах…
Вот такое решение про бочки с рабами...
Делим бочки для рабов на массивы по 48 + по 8 из каждого чужого, только что-бы не повторялись.
1 день каждому рабу по 48+8+8+8+8 бочек.
2 день если умер 1 то это только его собственные бочки из которых пил толко он, если умерло 2, то смотря каких( но это не важно, просто берем ту партию 8ми бочек), каждому оставшимуся по 2+1(т.е. тут едлим на кажого по 2 бочки своих + одана соседа, при этом они не должны пить из этих бочек больше 2х раз, т.е. каждый пьет только 1 раз).
Если в 1 день умерло 2, то одну из 8ми бочек оставляем, а из других 7ми пьют оставшиеся 3 раба так, что каждый пьет из 2х своих и 1 чужой, при этом опять без повторов(т.е. каждый раб пьет 3 раза из 3х бочек).
В итоге получаем если из этих 3х умрут 2, то пили из одной бочки, если один, то ипл из своей, а если ни одного, то отравлена оставшаяся бочка.
При этом потери рабов составляют от 1 до 4ех=)
И опять я, по шнурам...=)
Кладем паралельно оба шнура. Поджигаем их одновременно так, что-бы когда они прогорят до совмещения, т.е. до такого момента, что если сложить длины остатков, то получится целый шнур. Время которое пройдет будет равно 45минутам.
_1 день каждому рабу по 48+8+8+8+8 бочек._
Первый угостил второго своими 8-ю бочками, второй угостил первого своими 8-ю бочками. Если умерли оба - у них всего 16 общих бочек, а не 8. Решение не годится.
Да задачка в пять секунд - пусть каждый раб пьет через пол чяса из разных бочек 240/5, который помрет - отматать процесс на 24 и в бочку =)
По больше бы таких задачек - очень нра! спасибо =)
Если утверждение, что рабы могут сдохнуть в течение 24 часов после пробы вина, причем время, прошедшее от пробы до смерти, индивидуально (т.е. разное) для каждого раба, верно, то задача решения, как мне кажется, не имеет. В самом деле, исходя из этого предположения, максимум у нас есть 2 пробы: сначала и через 24 часа. Пробы, осуществляемые по ходу первых (к примеру) 24 часов смысла не имеют, т.к. не понятно как определить результат. Напр. сдохли 2 раба, кто знает от какой бочки? Может два раба пили из отравленной бочки, один сдох на месте, другой через 24 часа, а решение нужно принимать сейчас.
На 2 пробы тут не хватает рабов, т.к. тут 3чная система не катит (нету 3го состояния -- надо определять на месте умер раб или нет, и думать, что делать дальше), максимум, что можно отсюда выжать, так это 2 раза применить 2чную систему, но это только 64 бочки.
Ответ! Тк в условии сказано что смерть настает в течении 24 часов и то что через 48 часов бал,
а всего 5 рабочих чтоб проверить бочки,нужно понять и двигаться от обратного.
Те кароль узнал что смерть приходит в течении 24 часов от одного из рабов,
те 72 часа до бала у него после поимки вора было 6 рабов,за 48 часов осталось 5 рабов и всего 40 бочек,за 24 часа осталось 4 раба и 8 бочек.
далее идет лог формула,допустим,назавер рабов цифрами 1,2,3,4 бочки назавем буквами а б в г д е ж з и,:
Далее формула-
1а 2в 3д 4з
2б 3г 4ж 1и
3а 4в 1д 2з
4б 1г 2ж 3и
Итог остаеться бочка с ядом и всего 2 рабочих!!!
Кратко но с решением!!!
букву е не надо я описался
А Б В Г Д Ж З И
Не читал верхние комменты, честно :) Всего за первую проверку количество бочек можно разбить на 2^5 = 32 группы. Осталось определить, сколько бочек находится в каждой группе. 1 группа с 0 рабами - максимум 2^5 = 32, 5 групп с 1 рабом - 2^4 = 16, 10 групп с 2 рабами - 2^3 = 8, 10 групп с 3 рабами - 2^2 = 4, 5 групп с 4 рабами - 2^1 = 2, 1 группа с 5 рабами - 2^0 = 1. Итого выходит возможное количество проверяемых бочек = 243 > 240. Если не задействовать группы по 4 и 5 рабов - получается 240.
Читал, читал, устал, у каждого свое мнение, не знаю дал кто то правильный ответ или нет. Но насчет ответа по поводу 240 бочек. Возьмем первые 24 часа. Пусть вне зависимости от того когда кто выпьет, умрет раб на 24 часу. На каждого раба по 48 бочек(группа1). пусть в какой то группе есть бочка с ядом. По идеи кто то должен умереть. остальные откидываем. в первые же 24 часа, в той группе где приблизительно есть яд - 48 бочек( группа 2) остаются на оставшихся 4 рабов. на каждого по 12 бочек. Кто то из этой группы умирает, остальные откидываем, остается 3 раба на 12 бочек. А они все пьют и пьют, откуда такое здоровье. Из этих же 12 бочек в первый день выпивает каждый оставшийся (осталось 3 раба) по 4 бочки. Остается 2 раба. которые ждут следующего дня. по истечение первых суток у нас есть 4 бочки. вот эти 4 бочки распределяются между рабами в следующем порядке. 1 бочку выпивает 1 раб, 2 бочку выпивает 2 раб, 3 бочку выпивает 1 и 2 раб. 4 бочку никто. После окончания второго дня и узнаем остался кто то жить или нет.
Меня лично к этому ответу привели мысли всех вас. У каждого свое мнение, объединивши их месте получился результат. Спасибо за совместный разум.
Общее количество бочек 240
Первые 24 часа выпивает каждый раб из каждой подгруппы
1 группа 48 48 48 48 48 48 240/5
2 группа 12 12 12 12 12 12 48/4
3 группа 4 4 4 4 4 4 12/3
Получается каждый раб выпьет из 64 бочек и умрет максимум 3 раба,
Остало четыре
1 раб – 1 бочка
2 раб – 2 бочка
1,2 рабы – 3 бочка
Не тронутая 4 бочка
Зависит кто то умрет или нет вот и узнаем кто будет жить а кто не будет
Про таблетки:
если 1 пачка весит 1г, а такая же, но бракованная 1.01г, то можно положить на весы первую пачку и посмотреть ее вес. Если она весит 1г, то это не бракованная, ложим сверху еще 1 пачку, если в сумме они дадут 2г, то бракованная пачка та, которая не взвешивалась. Иначе та, которую докладывали сверху :)
Поздновато (только что наткнулся на задачку), но всё же целиком такое решение ещё никто не озвучил :)
Делим бочки на группы по 48 в каждой. Делим в каждой группе бочки на 5 подгрупп по 12, 9, 9, 9, 9 бочек.
Из группы 1 даём вино рабу 1. Из четырёх её подгрупп по 9 бочек даем остальным четырём рабам. Из подгруппы в 12 бочек не даём больше никому.
Делаем то же самое для остальных групп по 48. Таким образом, через 24 часа у нас известна группа из 48 бочек, где есть одна отравленная. Соответствующий раб умирает.
Далее - два варианта:
1)
Умрёт так же и тот раб, который попробовал вино из подной из подгруппы в 9 бочек. Тогда остаётся 9 подозрительных бочек и 3 раба. Действуем аналогично, т.е. делим 9 бочек на группы по 3, даём из каждой группы одному рабу из из двух подгрупп по 1 бочек двум другим рабам. Если умрут два раба - нашли бочку. Если умер 1 раб, значит, отравленное вино в соответствующей группе из 3-х бочек, и в той бочке, которую не пробовали два других раба.
2)
Остальные рабы не умирают. Значит, у нас есть 12 бочек, одна из которых - отравленная, и 4 живых раба. Делим бочки на 4 подгруппы по 3... ну и дальше ясно.
--
Заметим, что на шаге 2 у нас рабов больше, чем достаточно, т.е. имеет место избыточность по ресурсам :) Если ли бы бочек было не 12, а 16, то избыточности бы не было: 16 делим на подгруппы 4+4+4+4, даём из первой одному рабу, её делим на 1+1+1+1 и трём других рабам даём из соответствующей бочки... и т.п.
Таким образом, максимальное количество бочек, которое можно определить с помощью 5 рабов, составляет 5 * (16 + 9 + 9 + 9 + 9) = 260.
Программисты :) Можно любое количество бочек протестировать. Достаточно улучшить метод со временем. Один раб пьет каждые пять секунд и бочки - 12 тестов в минуту, 720 тестов в час. От времени смерти отнимаем 24 часа и количество секунд делим на 5. Все. Если хочется дать рабу шанс, то можно ему дать выпить из 239 бочек. Четыре оставшихся раба заберу себе - пригодятся :)
Павел Коршиков
Павел Коршиков
Программисты :) Можно любое количество бочек протестировать. Достаточно улучшить метод со временем. Один раб пьет каждые пять секунд и бочки
Программисты заметили фразу "человек, его выпивший, умирает в течение 24 часов". Ключевые слова "в течение".
У Evgeny 2 ошибки
1. 3 раба не могут проверить 9 бочек.
это можно было бы исправить если бы было бы 16,8,8,8,8 , но вторая ошибка(по хронологии первая) все равно ведет к неопределенности.
2. Если умирают 2 раба то у нас две группы по 8 бочек(в исходном тексте 9) , а не одна группа.
@Shtirlic: Нда, согласен - налажал... Хорошая вещь code review :)
В этой задачке если бы сразу было указано 243 бочки, то наверное было бы проще её решать, а так в начале посты с решением 243 почти не читал, только после того как решил понял, что её уже действительно решили :)
Правильный ответ посмотрю потом. Я понял задачу чётко по-программистски, а именно: попробовавший яд раб умирает ровно через 24 часа, ни часом раньше, ни часом позже. Тогда решение очень просто. Даём каждому рабу попробовать из своей бочки: первому из первой, второму из второй ... и засекаем время. Через полчаса первому рабу даём из шестой бочки, второму из седьмой, ... В общем, пока кто-нибудь не помрёт. Общее время, за которое рабы попробуют изо всех бочек (240/5)*0,5=24 часа + ещё 24 часа на то, чтобы кто-нибудь из них помер, если яд окажется в последней партии бочек. Когда помер, вспоминаем, из какой бочки давали ему пробовать ровно 24 часа назад... Всё, побежал смотреть правильное решение.
Отправить комментарий