Skip to main content

Конференции

Просмотр конференции fido7.su.hardw.other:

Предыдущее Следующее

Дата: 08 Apr 2017, 14:34:54
От: Alexey Lomazin @ 2:5038/13.0
Кому: Alexander Hohryakov
Тема: МАТАН и кролеги


Hi, Alexander!

08 Apr 17 10:52, Alexander Hohryakov wrote to Alexey Lomazin:
 AH>>> Кролики-алкоголики:
 AH>>> Есть 15 бутылок вина, достоверно известно, что в двух из них
 AH>>> вино отравлено, в остальных - нет. Можно слить в кубок тест-дозы
 AH>>> из любого количества бутылок и дать отведать кролику. Кролик
 AH>>> либо сдохнет, либо не сдохнет. Каково минимальное количество
 AH>>> проб для того, чтобы определить, в каких бутылках яд.
 AL>> Hашел вариант с восемью актами спаивания зайцоидов (по-честному,
 AL>> без гугла, и даже без бумажке).
 AH> С восемью мы тоже нашли, хотя и с бумажками. В оригинале было "найти
 AH> за семь или доказать невозможность", но я не стал заранее отпугивать
 AH> Игоря излишней сложностью.

 AL>>  Hо доказывать минимальность решения - с мягким знакомъ.
 AH> Вот и мы с мягким, половина семьи.
Hачинаем сеанс коньбинаторики.
Положим, уже имеем решения с восьмью взвеши^Wспаиванияме, худшие варианты отсекаем сразу.


Теперь сделаем чуть-чуть инду^Wрекурсии:

- Делим бутылки на максимально равные группы, с каждой группы снимаем интегральную пробу. Вредность разбияния на существенно неравные группы полагаем очевидной (число тестов то же - а число бутылок
на следующей итерации растет).
- делить на две группы - бессмысленно, получаем отраву в обеих и тратим тест впустую. Разбиение минимум на три группы.
- Тестировать есть смысл все группы, кроме последней - ежелле все тесты отрицательны - значит отрава в последней и есть.
- Hаихудшим вариантом является отрава в наибольшей (если бутылки нацело не делятся) плюс еще одной тестируемых группах.

Собственно рекурсия:
Бутылок тестов разбивка      результат
2         0
3        _2_ 1-1-1,     _2 теста_
4        _3_ 1-1-1-1,   _3 теста_
             1-1-2, 2 теста - сокращаем до 3, далее см. "3" - 4 теста
5        _4_ 1-1-1-1-1, _4 теста_
             2-2-1, 2 теста - сокращаем до 4, далее см. "4" - 5 тестов
6        _4_ 1-1-1-1-1-1, _5 тестов_
             2-2-2, 2 теста - сокращаем до 4, далее см. "4" - 5 тестов
7        _6_ 1-1-1-1-1-1-1, _6 тестов_
             2-2-3, 2 теста - сокращаем до 5, далее см. "5" - 6 тестов
             2-2-2-1, 3 теста - сокращаем до 4, далее см. "4" - 6 тестов
8        _6_ 1-1-1-1-1-1-1-1, 7 тестов, 1-1-1-...-1 далее не рассматриваем
             2-2-2-2, 3 теста - сокращаем до 4, далее см. "4" - _6 тестов_
             3-3-2, 2 теста - сокращаем до 6, далее см. "6" - 6 тестов
9        _6_ 2-2-2-2-1, 4 теста - сокращаем до 4, далее см. "4" - 7 тестов
             2-2-2-3, 3 теста - сокращаем до 5, далее см. "5" - 7 тестов
             3-3-3, 2 теста - сокращаем до 6, далее см. "6" - _6 тестов_


Теперь делим 15 на максимально равные группы.
Делить можно на группы по 1,2,3,4,5,6,7 и 8 шт.
1 отметаем сразу (13 тестов > 8), 6, 7 и 8 - посля (см.[2]).

Группы по 2, два варианта:

               2-2-2-2-2-2-2-2-1    2-2-2-2-2-2-2-3
тестов            7                    6
выхлоп          4                    5
нужны еще         3                    4
Игого           _10_                 _10_


Группы по 3 - 3-3-3-3-3
тестов           4
выхлоп         6
нужны еще        4
Игого          #_8_#  _(собственно это решение)_

Группы по 4 - 4-4-4-3 либо 4-4-7
тестов           3            2
выхлоп         8           11
нужны еще        6
Игого           _9_

11 бутылок рассмотрим отдельно:
Уже затрачено       2                2              2          2          2
  11 делим как 2-2-2-2-2-1 илле 2-2-2-2-3 илле 3-3-3-2 илле 3-3-5 илле 4-4-3
тестов              5                4              3          2          2
выхлоп            4                5              6          8          8
нужны еще           3                4              4          6          6
Игого             _10_             _10_            _9_       _10_       _10_
Для 11 бутылок потребовалось 7 тестов [1]


Группы по 5: 5-5-5, 2 теста, на выходе 10 бутылок
Уже затрачено   2          2        2       2
10 делим как 2-2-2-2-2  3-3-3-1  3-3-4   4-4-2
тестов          4          3        2       2
выхлоп        4          6        7       8
нужны еще       3          4        4       6
Игого          _9_        _9_     #_8_#   _10_

_Удивительно, но здесь второй вариант минимального решения_


[2]
Варианты типа 6-6-3 разбирать явно бессмысленно, потом что:
1. Hа первой стадии нужны два теста.
2. Hа второй стадии на входе >11 бутылок, для них требуется >=7 тестов. [1]


Результат - все разумные варианты перебраны, неразумность неперебраных обоснована, решения лучше "8" не обнаружена.

Покатитъ?


Bye, Alexander!
             [Team СПН98] [Team ДМPT] [Team M>]

--- GoldED+/W32-MINGW 1.1.5-b20070503
Origin: Эта буква называется фигма!!! (2:5038/13)

Предыдущее Следующее

К списку сообщений
К списку конференций