[bert04]

Zara, zara, skoro

... Możemy to zrobić za pomocą testowych myszek.
... Jaką minimalną liczbę myszek trzeba poświęcić,

to dammy miał rację.

A nawet lepiej, przy dozie szczęścia może się obyć bez ofiar.
Bierzemy 999 myszek (ich liczba nie została ograniczona) i każdej dajemy spróbować z jednej butelki.
Padnie jedna lub żadna (gdyby zatruta była akurat ta 1000 butelka).

Chyba że znowy czegoś nie doczytałem

Faktycznie, jeżeli interpretować "poświęcić" nie jako "wykorzystać" ale "uśmiercić", to najlepszy efekt ma matryca jednowymiarowa. Minus jeden.

Ale zadanie miało też pytanie dodatkowe, co zrobić, jeżeli liczba zatrutych butelek nie jest określona. Tego jeszcze nikt nie podjął.

---

EDIT:

Mamy do podania gościom na przyjęciu 1000 butelek wina. Jedno z nich jest jednak zatrute, a że nie chcemy nikogo otruć, próbujemy namierzyć trefną butelkę.

Jeżeli brać zadanie ultra-dosłownie, to jest ono niewykonalne. Po wyrzuceniu jednej butelki mamy ich 999, więc cel podania 1000 butelek wina jest nieosiągalny.

Oczywiście można zadanie przekształcić w "1000 minus te zatrute". To jest oczywiste dla jednej butelki, ale przestaje być dla liczby nieokreślonej. Wariant jednowymiarowy (999 myszek) prowadzi do dokładnego namierzenia, ale też do maksymalnej liczby ofiar. W wariantach wielowymiarowych możemy ustalić, że wylewamy całą "płaszczyznę" sprawdzania, jeżeli jedna mysz zdechnie. Przy odrobinie szczęścia pozostanie nam parę butelek, które nie były w jakimś podzbiorze zatrucia. Przy odrobinie pecha wylewamy wszystko i kupujemy 1000 butelek na allegro. Ale tu bez podania jakichś górnych pułapów zatrucia vs. wyrzucania trudno o optymalizację.

---

EDIT 2:

Jeżeli więc zdechły myszy druga, trzecia, siódma i dziesiąta, to szukamy butelki 0110001001, czyli 393.

W wariancie "matrycowym" wyrzucamy butelki z każdą kombinacją tych myszy. Ponieważ zdechły 4 myszy, wyrzucamy 4^2-1=15 butelek. Konkretnie:

1
8
9
128
129
136
137
256
257
264
265
384
385
392
393

To chyba tyle. Ponieważ butelek jest mniej niż 1024, nie będzie przypadku 1111111111, więc parę butelek nam zostanie.

EDIT 3:

Maksymalna liczba zatrutych myszy: 10. Jeżeli zostanie przynajmniej jedno zero, to wyrzucamy 511 butelek (przykładowo dla 0111111111), zostaje nam 489. Jeżeli mamy pecha, wyrzucamy cały skład.