Comments 29
нумеруем все бутылки в двоичном коде. выстраиваем кроликов по порядку и даем им отпить из нужных бутылок в зависимости от того 0 или 1. ну и ждем 21 день.
ясно что 10 кроликов хватит на 1024 бутылки :)
ясно что 10 кроликов хватит на 1024 бутылки :)
Позволю себе пояснить ваш ответ :)
Допустим у нас есть 4 бутылки и 2 кролика, тогда:
кролики 1 2
бутылки
0 0 0
1 0 1
2 1 0
3 1 1
В этой таблице там, где стоят единицы кролики должны пить, т.е. 1-ый кроли пьет из 2,3 бутылки; а 2-ой из 1,3 бутылки.
В зависимости от того какие кролики пострадают вычисляем исходную бутылку.
Допустим у нас есть 4 бутылки и 2 кролика, тогда:
кролики 1 2
бутылки
0 0 0
1 0 1
2 1 0
3 1 1
В этой таблице там, где стоят единицы кролики должны пить, т.е. 1-ый кроли пьет из 2,3 бутылки; а 2-ой из 1,3 бутылки.
В зависимости от того какие кролики пострадают вычисляем исходную бутылку.
Как-то криво вставилась таблица :(
а если яд был в 4-й бутылке? ))
скорее всего Ваша измененная задача про 4 бутылки и 2 кролика не имеет решения
не даром в оригинале предлагается 1000 бутылок на 10 кроликов, а не 1024
скорее всего Ваша измененная задача про 4 бутылки и 2 кролика не имеет решения
не даром в оригинале предлагается 1000 бутылок на 10 кроликов, а не 1024
если яд был в четвертой (3-ей, т.к. в таблице нумерация с нуля), погибнут оба кролика. Таблица действительно вставилась криво, но для понимания принципа это не мешает. Десятка кроликов с избытком хватит для тысячи бутылок.
Совершенно верно.
Простите за офтоп, но как надо было правильно вставлять таблицу?
Я выранивал пробелами, но несколько пробелов подряд почему-то заменились на один.
Простите за офтоп, но как надо было правильно вставлять таблицу?
Я выранивал пробелами, но несколько пробелов подряд почему-то заменились на один.
«почему-то» :)
это все таки браузер, а в html, несколько подряд идущих пробелов отображаются как один.
это все таки браузер, а в html, несколько подряд идущих пробелов отображаются как один.
Попробуйте воспользоваться табличными тегами. Выравнивание пробелами вряд ли подойдет, даже если использовать pre — шрифт не моноширинной.
Ну например так (не забывая тыкать кнопку «предпросмотр»):
12 23 34 1 2 3
<pre>Таблица, выровненная пробелами</pre>спасибо за объяснение :)
Ну и задача в чем? Так как она поставлена, ну хватит и одного кролика, давать ему воду из всех бутылок подряд, на которой ему станет плохо в той и яд!
Если яд начинает действовать ерез неизвестный промежуток времени, не более 20 дней, то так и нужно написать.
Если яд начинает действовать ерез неизвестный промежуток времени, не более 20 дней, то так и нужно написать.
Требую добавления пункта к задаче — не один кролик не должен пострадать
Если кролик вдруг начнёт закатывать глазки, дёргать лапами и проявлять желание отправиться на небо, то можно дать ему антидот и посчитать за погибшего. А на бутылке с антидотом добавить чёрточку :)
>>Яд действует достаточно долго, но не дольше, чем 20 дней.
Я это расцениваю как в играх, отравили — пей антидот. Нет антидота, будет какое-то время(20 дней) отниматься hp, если hp много останешься в живых.
Так кролик должен умирает или нет? и действие яда видно сразу или только тогда когда кролик умрет?
Я это расцениваю как в играх, отравили — пей антидот. Нет антидота, будет какое-то время(20 дней) отниматься hp, если hp много останешься в живых.
Так кролик должен умирает или нет? и действие яда видно сразу или только тогда когда кролик умрет?
Если без шуток, то подразумевается, что яд убивает насмерть. В первый день надо по искомому алгоритму отравить кроликов, и, выпившие из бутылки с ядом, будут умирать случайным образов в любой из 20 ближайших дней. Таким образом, к 21-му дню станет окончательно ясно, кто умер — тот отпивал из бутылки с ядом.
Главное, чтобы их можно было после этого есть! Если нет, звоню в гринпис!
Один шанс из тысячи, что ни один кролик не пострадает
Это получается, если отравлена бутылка под номером 512, погибнет 9 кроликов из 10? Куда смотрит Гринпис…
Такой вопрос задавали на собеседовании если не ошибаюсь в компанию AVIcode в Питере. Заставляет подумать)
про двоичный код не подумал, т.к. не программист, а во на ум пришла ассоциация с рулеткой в казино, точнее с зонами на игровом поле: красное/чёрное, чёт/нечет и т.д.
т.е. действовать надо примерно так: первого кролика весь день поить только из чётных бутылок (сдохнет через месяц — значит яд в одной из чётных, не сдохнет — в нечётной)
второго кролика поить только из первых пятиста. Уже так уменьшаем кол-во угадываемых бутылок до 250ти.
прежде чем мучать третьего кролика, маркируем бутылки: половину чётных (250 штук) отмечаем красным маркёром, другую половину чёрным. Так же метим нечётные. после этого даём третьему кролику выпить «красный» коктейльчик, уменьшая количество неизвестных бутылок до 125.
И тут до меня дошло, что действительно, придётся к нашей тысяче докупить ещё обычных с водой бутылок в количестве 24, чтобы было удобно считать. Ну а принцип тот же: разделить все бутылки поравну по 10ти признакам (чёт/нечет, цвета, крестики/нолики и т.п.), и чтобы равномерно.
Ну я если в задаче именно тысяча бутылок… то можно вместо 24х дополнительных бутылок подписать на тетрадном листочке «бутылка» и использовать его для ровного счёта, чтобы не держать их в уме.
Так же важно понимать, в каких дозах яд проявляет себя, т.е. сколько яду должен выпить кролик, чтобы по нему через 20 дней можно было сказать, что он отравился (там, чесаться начал, волосатость повысилась, и т.п.)
Ведь даже если кролику достаточно всего 5мл, то это значит, что каждому придётся споить за день 5 литров жидкости, причём не смешивая, чтобы не разбавлять яд, а по чайной ложечке из каждой их пятиста бутылок…
т.е. действовать надо примерно так: первого кролика весь день поить только из чётных бутылок (сдохнет через месяц — значит яд в одной из чётных, не сдохнет — в нечётной)
второго кролика поить только из первых пятиста. Уже так уменьшаем кол-во угадываемых бутылок до 250ти.
прежде чем мучать третьего кролика, маркируем бутылки: половину чётных (250 штук) отмечаем красным маркёром, другую половину чёрным. Так же метим нечётные. после этого даём третьему кролику выпить «красный» коктейльчик, уменьшая количество неизвестных бутылок до 125.
И тут до меня дошло, что действительно, придётся к нашей тысяче докупить ещё обычных с водой бутылок в количестве 24, чтобы было удобно считать. Ну а принцип тот же: разделить все бутылки поравну по 10ти признакам (чёт/нечет, цвета, крестики/нолики и т.п.), и чтобы равномерно.
Ну я если в задаче именно тысяча бутылок… то можно вместо 24х дополнительных бутылок подписать на тетрадном листочке «бутылка» и использовать его для ровного счёта, чтобы не держать их в уме.
Так же важно понимать, в каких дозах яд проявляет себя, т.е. сколько яду должен выпить кролик, чтобы по нему через 20 дней можно было сказать, что он отравился (там, чесаться начал, волосатость повысилась, и т.п.)
Ведь даже если кролику достаточно всего 5мл, то это значит, что каждому придётся споить за день 5 литров жидкости, причём не смешивая, чтобы не разбавлять яд, а по чайной ложечке из каждой их пятиста бутылок…
Если на всех кроликов яд действует за одинаковое время, то есть стратегия по сокращению потерь среди мирного ушастого населения.
Маркируем бутылки от 000 до 999. Соответственно значение разряда обозначает кролика.
В первый час кролики пьют бутылки по соответствию старшему разряду (так первый(нулевой) кролик пьет воду из первой сотни бутылок), во второй час — по среднему разряду, в третий — по младшему.
В итоге в какой то момент у нас начнут по очереди дохнуть кролики. Если по очереди сдохнут первый, второй и третий кролики, значит яд в бутылке 012.
В итоге максимальные потери — 3 ушастых… ;)
З.Ы. Если яд действует на кроликов по разному, то мы в худшем случае получим выбор из 6 бутылок. Что тоже неплохо. ;)
Маркируем бутылки от 000 до 999. Соответственно значение разряда обозначает кролика.
В первый час кролики пьют бутылки по соответствию старшему разряду (так первый(нулевой) кролик пьет воду из первой сотни бутылок), во второй час — по среднему разряду, в третий — по младшему.
В итоге в какой то момент у нас начнут по очереди дохнуть кролики. Если по очереди сдохнут первый, второй и третий кролики, значит яд в бутылке 012.
В итоге максимальные потери — 3 ушастых… ;)
З.Ы. Если яд действует на кроликов по разному, то мы в худшем случае получим выбор из 6 бутылок. Что тоже неплохо. ;)
g fdsg dsg
Есть более изящное решение!
Мысленно разместим бутылки по ячейкам куба 10x10x10 (всего 1000 ячеек — на каждую по бутылке).
Расставим кроликов в ряд у одной из граней куба и пронумеруем их от 10 до 10. Каждый кролик выпьет из каждой из 100 бутылок, находящихся в вертикальном квадрате, перпендикулярном данному кролику. Повернем куб на 90 градусов по одной из осей и повторим операцию с отпиванием из 100 бутылок. И наконец, повернем куб на 90 градусов по другой оси и снова каждый кролик выпьет из 100 стоящих перед ним бутылок.
Вот картинка для третьего кролика:
Таким образом каждый кролик выпивает из 300 бутылок (на самом деле меньше, но для решения — не важно). На 21й день найдем от 1 до 3 охладевших тушек. По номерам кроликов легко найдем из какой бутылки они вместе выпили.
Мысленно разместим бутылки по ячейкам куба 10x10x10 (всего 1000 ячеек — на каждую по бутылке).
Расставим кроликов в ряд у одной из граней куба и пронумеруем их от 10 до 10. Каждый кролик выпьет из каждой из 100 бутылок, находящихся в вертикальном квадрате, перпендикулярном данному кролику. Повернем куб на 90 градусов по одной из осей и повторим операцию с отпиванием из 100 бутылок. И наконец, повернем куб на 90 градусов по другой оси и снова каждый кролик выпьет из 100 стоящих перед ним бутылок.
Вот картинка для третьего кролика:
Таким образом каждый кролик выпивает из 300 бутылок (на самом деле меньше, но для решения — не важно). На 21й день найдем от 1 до 3 охладевших тушек. По номерам кроликов легко найдем из какой бутылки они вместе выпили.
хотя это и и не так «айтишно», как двоичный метод из первого коммента, но это круто. еще и кролики экономятся.
P.S.: а вы долго решали :)
P.S.: а вы долго решали :)
Метод решения — неверный. Проблема в том, что эта бутылка будет не единственной.
Предположим, погибло три кролика, за номерами 1, 2 и 3.
Давайте на вашем же кубике дорисуем бутылки, которые выпили ещё 2 погибших кролика: бутылки первого кролика обозначим жёлтым цветом, бутылки второго — синим.
Чёрным помечены бутылки, из которых пили все три погибших кролика, и больше никто.
Их несколько, а значит — задача не решена.
Предположим, погибло три кролика, за номерами 1, 2 и 3.
Давайте на вашем же кубике дорисуем бутылки, которые выпили ещё 2 погибших кролика: бутылки первого кролика обозначим жёлтым цветом, бутылки второго — синим.
Чёрным помечены бутылки, из которых пили все три погибших кролика, и больше никто.
Их несколько, а значит — задача не решена.
Sign up to leave a comment.
Задача про кроликов и яд.