Вы, правитель империи, решили устроить пир, который состоится ровно через один месяц. Чтобы обеспечить застолье должным количеством вина, вами было приказано от каждой провинции доставить к императорскому двору по одной бочке с вином. В империи 1000 провинций... — 1000 бочек уже стоят в вашем погребе, все прекрасно. Но ваши разведчики внезапно долкладывают вам о том, что в одной из бочек вино отравлено, естесственно неизвестно в какой. Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает. Нужно точно определить к началу пира в какой бочке яд и не допустить вымирания правящей династии.
Есть 2 постановки вопроса для решения:
1. Какое минимальное число слуг можно задействовать и как?
2. Какое минимальное количество вина можно израсходовать и как?
Здравствуйте, HeaveN, Вы писали:
HN>Задачка такая пробежала...
HN>Вы, правитель империи, решили устроить пир, который состоится ровно через один месяц. Чтобы обеспечить застолье должным количеством вина, вами было приказано от каждой провинции доставить к императорскому двору по одной бочке с вином. В империи 1000 провинций... — 1000 бочек уже стоят в вашем погребе, все прекрасно. Но ваши разведчики внезапно долкладывают вам о том, что в одной из бочек вино отравлено, естесственно неизвестно в какой. Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает. Нужно точно определить к началу пира в какой бочке яд и не допустить вымирания правящей династии. HN>Есть 2 постановки вопроса для решения:
HN>1. Какое минимальное число слуг можно задействовать и как?
Представим номера бочек в двоичном виде (0 = дегустатор N не отпивает, 1 = дегустатор N отпивает), для этого понадобиться 10 разрядов-дегустаторов (2^10 = 1024). Чтобы при этом минимизировать кол-во выпитого вина можно похитрить с кодировкой, но экономия будет копеечная.
HN>2. Какое минимальное количество вина можно израсходовать и как?
999 дегустаторов, каждый отпивает по 1 стакану из персональной бочки.
Здравствуйте, HeaveN, Вы писали:
HN>Задачка такая пробежала...
HN>
Вы, правитель империи, решили устроить пир, который состоится ровно через один месяц. Чтобы обеспечить застолье должным количеством вина, вами было приказано от каждой провинции доставить к императорскому двору по одной бочке с вином. В империи 1000 провинций... — 1000 бочек уже стоят в вашем погребе, все прекрасно. Но ваши разведчики внезапно долкладывают вам о том, что в одной из бочек вино отравлено, естесственно неизвестно в какой. Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает. Нужно точно определить к началу пира в какой бочке яд и не допустить вымирания правящей династии.
HN>Есть 2 постановки вопроса для решения:
HN>1. Какое минимальное число слуг можно задействовать и как?
HN>2. Какое минимальное количество вина можно израсходовать и как?
Раасмотрим общий случай:
Пусть N — количество бочек, а K — количество слуг.
для каждой бочки строим вектор из K элементов: в этом векторе i-ый элемент
равен 1, если слуга номер i выпил стакан из этой бочки. Если не выпил, то 0.
Таким образом, имеем N штук векторов.
Для того, чтобы обнозначно идентифицировать бочку надо, чтобы никакие два
из этих векторов не были идентичны.
Т.е. нам нужно N штук различных двоичных векторов длины K.
отсюда минимальное K = [log2(N)] + 1
То есть в нашем случае минимальное количество слуг — 10.
Если наша задача — минимизировать количество выпитого вина, то тогда решение
тривиально — 999 слуг. Т.к. из 999 бочек нужно выпить как минимум 1 стакан,
чтобы определить отравленную бочку.
Здравствуйте, HeaveN, Вы писали:
HN>Задачка такая пробежала...
HN>
Вы, правитель империи, решили устроить пир, который состоится ровно через один месяц. Чтобы обеспечить застолье должным количеством вина, вами было приказано от каждой провинции доставить к императорскому двору по одной бочке с вином. В империи 1000 провинций... — 1000 бочек уже стоят в вашем погребе, все прекрасно. Но ваши разведчики внезапно долкладывают вам о том, что в одной из бочек вино отравлено, естесственно неизвестно в какой. Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает. Нужно точно определить к началу пира в какой бочке яд и не допустить вымирания правящей династии.
HN>Есть 2 постановки вопроса для решения:
HN>1. Какое минимальное число слуг можно задействовать и как?
HN>2. Какое минимальное количество вина можно израсходовать и как?
Всё просто — если нужно сохранить только династию, то можно наплевать на гостей,
взять одного слугу и заставить выпить один стакан. Помрет — зашибись, не помрет — бочки на династию хватит.
PS если династия большая — то сосчитать необходимое количество бочек...
HeaveN wrote: > > Задачка такая пробежала... > > [q]Вы, правитель империи, решили устроить пир, который состоится ровно через один месяц. Чтобы обеспечить застолье должным количеством вина, вами было приказано от каждой провинции доставить к императорскому двору по одной бочке с вином. В империи 1000 провинций... — 1000 бочек уже стоят в вашем погребе, все прекрасно. Но ваши разведчики внезапно долкладывают вам о том, что в одной из бочек вино отравлено, естесственно неизвестно в какой. Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает. Нужно точно определить к началу пира в какой бочке яд и не допустить вымирания правящей династии. > Есть 2 постановки вопроса для решения: > > 1. Какое минимальное число слуг можно задействовать и как?
А сколько вина в состоянии несчастный слуга выпить за один день ? Если
ему споить 1000 стаканов — помрет, даже если не отравлено
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А сколько вина в состоянии несчастный слуга выпить за один день ? Если PD>ему споить 1000 стаканов — помрет, даже если не отравлено
Это ничего не даст — по условиям задачи он умрет ровно через месяц. И неизвестно, из-за какого именно стакана.
Здравствуйте, HeaveN, Вы писали:
HN>1. Какое минимальное число слуг можно задействовать и как?
0
HN>2. Какое минимальное количество вина можно израсходовать и как? [/q]
0
как?
пронумеруем бочки от 1 до 1000.
в бочке под номером 666 вино отравлено!
Здравствуйте, HeaveN, Вы писали:
HN>Задачка такая пробежала...
HN>Вы, правитель империи, решили устроить пир, который состоится ровно через один месяц. Чтобы обеспечить застолье должным количеством вина, вами было приказано от каждой провинции доставить к императорскому двору по одной бочке с вином. В империи 1000 провинций... — 1000 бочек уже стоят в вашем погребе, все прекрасно. Но ваши разведчики внезапно долкладывают вам о том, что в одной из бочек вино отравлено, естесственно неизвестно в какой. Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает. Нужно точно определить к началу пира в какой бочке яд и не допустить вымирания правящей династии. HN>Есть 2 постановки вопроса для решения:
HN>1. Какое минимальное число слуг можно задействовать и как?
10 слуг. Для примера берем 8 бочек. Составляем таблицу:
01010101
00110011
00001111
Для каждой бочки свой столбец, для каждого слуги — своя строка. Слуга выпивает по стакану в соответствии с таблицей, а через месяц вычисляем бочку.
HN>2. Какое минимальное количество вина можно израсходовать и как?
Берем 1000 слуг и каждый по стакану выпивает из своей бочки. Через месяц смотрим, который из них скопытится.
Еще вариант: смешиваем все вина из всех бочек, и тогда концентрация яда будем несмертельной.
Блудов Павел wrote: > > Здравствуйте, Pavel Dvorkin, Вы писали: > > PD>А сколько вина в состоянии несчастный слуга выпить за один день ? Если > PD>ему споить 1000 стаканов — помрет, даже если не отравлено > > Это ничего не даст — по условиям задачи он умрет ровно через месяц. И неизвестно, из-за какого именно стакана.
Естественно, в таком виде это ничего не даст. Но мой вопрос в другом
заключается — сколько стаканов можно одному дать ?
К примеру, пусть всего 3 бочки
А пьет из 1 и 2
Б пьет из 2 и 3
В пьет из 3 и 1
Умрут А и В — отравлена 1-я, А и Б — вторая и т.д.
Я не говорю, что это хорошее решение, но ИМХО знать, сколько можно
споить каждому, необходимо.
--
With best regards,
Pavel Dvorkin
Posted via RSDN NNTP Server 1.8
With best regards
Pavel Dvorkin
Re[2]: Отравленное вино
От:
Аноним
Дата:
15.09.04 10:10
Оценка:
Боюсь что слуга, отвечающий за младший бит не выдержит, ведь ему придется выпить 500 стаканов
Здравствуйте, HeaveN, Вы писали:
HN>Задачка такая пробежала...
HN>[q]Вы, правитель империи, решили устроить пир, который состоится ровно через один месяц. Чтобы обеспечить застолье должным количеством вина, вами было приказано от каждой провинции доставить к императорскому двору по одной бочке с вином. В империи 1000 провинций... — 1000 бочек уже стоят в вашем погребе, все прекрасно. Но ваши разведчики внезапно долкладывают вам о том, что в одной из бочек вино отравлено, естесственно неизвестно в какой. Яд действует медленно и коварно — один месяц, и после этого выпивший хотя бы один стакан вина умирает. Нужно точно определить к началу пира в какой бочке яд и не допустить вымирания правящей династии. HN>Есть 2 постановки вопроса для решения:
HN>1. Какое минимальное число слуг можно задействовать и как?
Ставим бочки в виде матрицы 10 x 10 x 10 — при это нам потребуется 10 + 10 + 10 = 30 слуг, чтобы первые 10 слуг попробовали все бочки в соответсвующих строках (номер слуги = номер строки), вторые 10 — все бочки в столбцах, а третьи — по вертикали. Т.е. каждый слуга попробует "слой" из 100 бочек. При это умрут 3 слуги на, на пересечении номеров которых и находилась бочка с ядом.
Если пробовать 100 бочек силы нет, то можно ограничиться двумерной матрицей 32 x 32 = 1024 при этом 24 места оставим пустыми, и умрут только 2 слуги, а на каждого из 32 + 32 — 24 = 40 слуг придется по 32 бочки. Здесь нужно 64 слуги
Здравствуйте, Аноним, Вы писали:
А>Боюсь что слуга, отвечающий за младший бит не выдержит, ведь ему придется выпить 500 стаканов
И остальные тоже, так как практически каждому придеться пить почти 500 стаканов, а не одному!
Здравствуйте, sergey_shandar, Вы писали:
_>Здравствуйте, Аноним, Вы писали:
А>>Боюсь что слуга, отвечающий за младший бит не выдержит, ведь ему придется выпить 500 стаканов _>И остальные тоже, так как практически каждому придеться пить почти 500 стаканов, а не одному!
_>Первый — третий: 500 _>Четвертый: 500 — 8 = 492 _>Пятый — десятый: 500 — 24 = 476
Хорош жрать, мне оставьте
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Естественно, в таком виде это ничего не даст. Но мой вопрос в другом PD>заключается — сколько стаканов можно одному дать ?
Ну литров 10 в день сможет любой. Если это вино — Сангрия. Если наливать по 20 грам, то будет 500 порций.
PD>К примеру, пусть всего 3 бочки
PD>А пьет из 1 и 2 PD>Б пьет из 2 и 3 PD>В пьет из 3 и 1
PD>Умрут А и В — отравлена 1-я, А и Б — вторая и т.д.
Тут хватит двух слуг: PD>А пьет из 1 и 2 PD>Б пьет из 2 и 3
Если умрет А значит 1-я.
Если умрет В значит 3-я.
Если оба значит 2-я.
Если никто значит 4-я.
