Поиски корня

[fortpost]

У Семёныча в погребе хранятся 1000 бутылок с живительным напитком. Но одна из них особо ценная, потому как в ней содержится настойка редчайшего корня хрень-бздень. Да вот беда - по рассеянности Семёныч забыл, где ее поставил. А между тем приближается знаменательная дата - 1234 дня пребывания Семёныча на Назве, кою необходимо достойно отметить. Чтобы помочь любимому деду, внучка раздобыла несколько белых мышек. Если мышке накапать в еду пару капель настойки чудесного корня, то она на другой день посинеет. Семёнычу необходимо как можно быстрее обнаружить заветную бутылку. Кроме того он хочет, чтобы как можно меньше бедных зверюшек мучились похмельем. Как же это можно сделать?

[Руслан Дехтярь]

У Семёныча в погребе хранятся 1000 бутылок с живительным напитком. Но одна из них особо ценная, потому как в ней содержится настойка редчайшего корня хрень-бздень. Да вот беда - по рассеянности Семёныч забыл, где ее поставил. А между тем приближается знаменательная дата - 1234 дня пребывания Семёныча на Назве, кою необходимо достойно отметить. Чтобы помочь любимому деду, внучка раздобыла несколько белых мышек. Если мышке накапать в еду пару капель настойки чудесного корня, то она на другой день посинеет. Семёнычу необходимо как можно быстрее обнаружить заветную бутылку. Кроме того он хочет, чтобы как можно меньше бедных зверюшек мучились похмельем. Как же это можно сделать?

Дата эта когда будет? Сколько дней до нее?
Иначе можно же одну мышку угробить. Напаивать, ждать сутки, смотреть посинеет или нет..И так до достижения нужного результата.

[fortpost]

Дата эта когда будет? Сколько дней до нее?
Иначе можно же одну мышку угробить. Напаивать, ждать сутки, смотреть посинеет или нет..И так до достижения нужного результата.

Судя по аке Семёныча, дата сия наступит 10 октября сего года. Так что времени остается чуть больше недели.

[семеныч]

  2  4  8  16  32  64 128  256   512 1024
 

   

[fortpost]

Семёныч, так ты небось знаешь эту задачу! Чур, не подсказывать! Не лишай народ удовольствия подумать.

[Руслан Дехтярь]

А мышь остается в синем состоянии навсегда?
То есть, если она посинела, ее уже нельзя использовать?

[Крипто]

Тут по моему обратная зависимость или быстрее и мышек много, или наоборот долго но мышка одна)))
Но вроде как:
Накапать 10 мышкам из 100 бутылок по 10.
На следующий день посинеет 1.
Итого остается 10 бутылок.
Из них накапать 10 мышкам по 1.
На следующий день посинеет 1, и мы узнаем какая бутылка нам нужна.
Итого 10 мышек с сильным похмельем и 10 из легким. Из них 2 синие)

[fortpost]

А мышь остается в синем состоянии навсегда?
То есть, если она посинела, ее уже нельзя использовать?

Может и не навсегда, но все ж достаточно надолго. В большинстве подобных задач так и вовсе копыта откидывают. Но мы ж не садисты. Значит, будем считать, что мыши одноразовые.

[fortpost]

Тут по моему обратная зависимость или быстрее и мышек много, или наоборот долго но мышка одна)))
Но вроде как:
Накапать 10 мышкам из 100 бутылок по 10.
На следующий день посинеет 1.
Итого остается 10 бутылок.
Из них накапать 10 мышкам по 1.
На следующий день посинеет 1, и мы узнаем какая бутылка нам нужна.
Итого 10 мышек с сильным похмельем и 10 из легким. Из них 2 синие)

Так можно, конечно. Но это не оптимальное решение. К тому же бутылок не 100, а 1000.

[Крипто]

...Но мы ж не садисты. Значит, будем считать, что мыши одноразовые.

Ну тогда используйте лакмусовые бумажки)))

[Крипто]

Как писал:

Тут по моему обратная зависимость или быстрее и мышек много, или наоборот долго но мышка одна)))

Или берем 999 мышек и за сутки.
Или берем 10 мышек и за 10 суток, узнаем результат...
В первый день, берем 1 мышку и капаем из 500 бутылок, если не посинела то на следующий день берем 250 из оставшихся 500. И так до результата. Мах 10 дней и 10 мышек.

[fortpost]

Как писал:

Тут по моему обратная зависимость или быстрее и мышек много, или наоборот долго но мышка одна)))

Или берем 999 мышек и за сутки.
Или берем 10 мышек и за 10 суток, узнаем результат...
В первый день, берем 1 мышку и капаем из 500 бутылок, если не посинела то на следующий день берем 250 из оставшихся 500. И так до результата. Мах 10 дней и 10 мышек.

И так тоже можно. Но и оно не оптимально.

[fortpost]

Что, здались все? Оптимальное решение пора давать?

[семеныч]

п
о
р
а

[fortpost]

Ну раз пора, так вот оно.
Показать скрытый текст

Приглашаем мышей за стол, садим их в ряд и напротив каждой ставим табличку с номером ее места от 0 до 9. Далее, берем бутылки по порядку, нумеруем и наливаем из каждой по капле тем мышам, которые сидят на местах, соответствующих единицам в двоичной записи номера бутылки. Например, первую бутылку наливаем мышке на месте 0 (1=2⁰), девятую -- мышам на 0-м и 3-м (9=2³+2⁰) и так далее. После того как отольем вина из всех бутылок, даем мышам выпить. Для определения номера искомой бутылки необходимо преобразовать получившееся двоичное число (мышка окрашена = 1, неокрашена = 0) в десятичную запись. Таким образом, укладываемся в одни сутки и десять мышей.

Семёныч, к твоей дате успеваем!