Недавно в Puzzling.SE я писал о проблеме, касающейся определения того, какие две бутылки из большего числа отравлены, когда яд активируется, только если оба компонента выпиты. В итоге это стало настоящим испытанием, и большинству людей удалось довести его до 18 или 19 заключенных, используя совершенно разные алгоритмы.
Первоначальное постановка задачи состоит в следующем:
Вы правитель средневекового королевства, который любит устраивать вечеринки. Придворный, который пытался отравить одну из твоих бутылок вина в прошлый раз, был в ярости, узнав, что тебе удалось определить, какую бутылку он отравил из 1000 с десятью заключенными.
На этот раз он немного хитрее. Он разработал сложный яд
P
: бинарную жидкость, которая смертельна только тогда, когда смешиваются два отдельных безвредных компонента; это похоже на то, как работает эпоксидная смола. Он отправил вам еще один ящик из 1000 бутылок вина. Одна бутылка имеет компонент,C_a
а другая имеет компонентC_b
. (P = C_a + C_b
)Любой, кто пьет оба компонента, умрет в полночь в ночь, когда выпил последний компонент, независимо от того, когда в день они пили жидкость. Каждый ядовитый компонент остается в организме до тех пор, пока не активируется второй компонент, поэтому, если вы пьете один компонент один день, а другой - следующий, вы умрете в полночь в конце второго дня.
У вас есть два дня до вашей следующей вечеринки. Какое минимальное количество заключенных вам нужно использовать для тестирования, чтобы определить, какие две бутылки испорчены, и какой алгоритм вы должны использовать с таким количеством заключенных?
Бонус
Кроме того, предположим, что в вашем распоряжении установлен фиксированный лимит в 20 заключенных, какое максимальное количество бутылок вы можете теоретически протестировать и прийти к точному выводу о том, какие бутылки были затронуты?
Ваша задача - построить программу для решения бонусной проблемы. Учитывая n
заключенных, ваша программа разработает график тестирования, который сможет обнаружить две отравленные бутылки среди m
бутылок, m
насколько это возможно.
Ваша программа первоначально будет принимать в качестве входных данных N
число заключенных. Затем он выведет:
M
количество бутылок, которое вы попытаетесь проверить. Эти бутылки будут маркированы от1
доM
.N
строки, содержащие этикетки бутылок, которые выпьет каждый заключенный.
Затем ваша программа будет принимать в качестве входных данных, какие заключенные умерли в первый день, с заключенным в первой строке 1
, следующей строкой 2
и т. Д. Затем будет выведено:
N
больше строк, содержащих этикетки бутылок, которые выпьет каждый заключенный. У мертвых заключенных будут пустые строки.
Затем ваша программа примет в качестве входных данных, какие заключенные умерли на второй день, и выведет два числа A
и B
, представляющих, какие две бутылки, по вашему мнению, содержат яд.
Пример ввода для двух заключенных и четырех бутылок может быть таким, если бутылки 1
и 3
отравлены:
> 2 // INPUT: 2 prisoners
4 // OUTPUT: 4 bottles
1 2 3 // OUTPUT: prisoner 1 will drink 1, 2, 3
1 4 // OUTPUT: prisoner 2 will drink 1, 4
> 1 // INPUT: only the first prisoner died
// OUTPUT: prisoner 1 is dead, he can't drink any more bottles
3 // OUTPUT: prisoner 2 drinks bottle 3
> 2 // INPUT: prisoner 2 died
1 3 // OUTPUT: therefore, the poisoned bottles are 1 and 3.
The above algorithm may not actually work in all
cases; it's just an example of input and output.
График тестирования вашей программы должен успешно определять каждую возможную пару отравленных бутылок, чтобы она была действительной отправкой.
Ваша программа будет оцениваться по следующим критериям:
Максимальное количество бутылок, которое он может различить для данного случая
N = 20
.Количество бутылок для кейса
N = 21
и последовательно более высокие кейсы после этого.Длина кода. (Короче код выигрывает.)
источник
Ответы:
Python 2.7.9 - 21 бутылка
Предполагая, что Е.С. Султаник прав в том, что является входом, когда умирают несколько заключенных
Алгоритм: каждый заключенный пьет из каждой бутылки, кроме их количества (1-й заключенный не пьет первую бутылку). Если они не умирают, их номерная бутылка отравлена. Если выживет только один заключенный, дополнительная бутылка отравлена.
источник
Perl 5 , 66 бутылок
(72 бутылки на 21 заключенного)
Заключенные оптимально поделены на 2 группы. Бутылки сгруппированы в наборы.
Каждый заключенный группы 1 будет пить из всех сетов, кроме одного. Там будет 1 или 2 выживших. 1 или 2 сета, которые они не выпили, будут продолжаться до второго дня.
На второй день оставшиеся заключенные (включая выживших) пьют из всех оставшихся бутылок, кроме одной.
Когда выживают 2 заключенных, бутылки, которые они не пили, отравляются.
Если остается только 1 заключенный, то бутылка, которую они все выпили, также является подозрительной.
Код включает дополнительную функциональность для облегчения тестирования. Когда добавленные бутылки добавляются в качестве дополнительных параметров, он не будет запрашивать информацию о том, кто умер.
Тестовое задание
Тест без ручного ввода
источник
По традиции я выложу последний справочный ответ.
Питон - 7 бутылок
Заставьте каждого заключенного выпить одну возможную пару бутылок, за исключением пары последних двух. Если кто-либо из заключенных умирает, пара, которую выпил этот заключенный, была отравленной. Иначе это были последние две бутылки, которые были отравлены.
Для выделений как минимум
n(n-1)/2 - 1
заключенных можно сделать доn
бутылок. Дляn = 7
, это нижний предел20
.Нам нужно только один день, чтобы это решение заработало. Двухдневное решение с аналогичной областью применения может потребовать до 20 бутылок
N = 20
, но это слишком много работы для тривиального ответа.источник