Трудный вопрос на собеседовании #1
developers.org.ua решили опубликовать замечательный цикл “Трудные вопросы на собеседовании” на русском языке. Каждую неделю будет публиковаться один новый вопрос, а также добавляться в комментариях ответ на предыдущий. Учитывая, что ответы на все эти вопросы есть в открытом доступе на сайте оригинала, цель, которую мы преследуем этим циклом переводов — дать возможность потренироваться тем, кто этого хочет, плюс пополемизировать на тему качества задач и их решений. Итак!..
Задача #1
Есть две деревни: деревня магов и деревня гномов. Раз в год маги проходят по деревне гномов и выстраивают их по росту в возрастающем порядке, так что каждый гном может видеть только тех, кто ниже его самого.
У магов неограниченное количество чёрных и белых шляп. Они одевают белую или черную шляпу на голову каждого гнома.
Затем, начиная с самого высокого гнома (в конце шеренги), они спрашивают его, какого цвета шляпа не нём надета. Если гном ошибается, маги убивают его (другие гномы слышат его ответ, но не могут определить, был ли он убит или нет).
Какой стратегии должны придерживаться гномы, чтобы минимизировать количество убиенных гномов?
Каково максимальное количество гномов, которые будут убиты при использовании оптимальной стратегии?
Источник http://www.developers.org.ua