Трудные вопросы на собеседовании, hard interview questions Опции

[compiler]

Добрый день!
Итак, один из ресурсов рунета решил опубликовать цикл ”Трудные вопросы на собеседовании” на русском языке. Каждую неделю там будет публиковаться один новый вопрос, а также добавляться в комментариях ответ на предыдущий. Учитывая, что ответы на все эти вопросы есть в открытом доступе на сайте оригинала, цель, которую преследуют этим циклом переводов — дать возможность потренироваться тем, кто этого хочет, плюс пополемизировать на тему качества задач и их решений.
Всего 33 вопрса. На англоязычном оригинали есть уже все ответы, но найти и посмотреть не спортивно, имхо... Русскоязычный аналог начал публикации 2.06. Перевод от Скакунова Александра.
В общем почему бы не продублировать цикл здесь?

Задача #1

Есть две деревни: деревня магов и деревня гномов. Раз в год маги проходят по деревне гномов и выстраивают их по росту в возрастающем порядке, так что каждый гном может видеть только тех, кто ниже его самого.

У магов неограниченное количество чёрных и белых шляп. Они одевают белую или черную шляпу на голову каждого гнома.

Затем, начиная с самого высокого гнома (в конце шеренги), они спрашивают его, какого цвета шляпа не нём надета. Если гном ошибается, маги убивают его (другие гномы слышат его ответ, но не могут определить, был ли он убит или нет).

Какой стратегии должны придерживаться гномы, чтобы минимизировать количество убиенных гномов?

Каково максимальное количество гномов, которые будут убиты при использовании оптимальной стратегии?

В атаче задание на ангельском.
Источники(русскоязычный и англоязычный), приложены из-за моральных соображений, просьба не смотреть..

Спойлер (Показать/Скрыть)

http://www.developers.org.ua/archives/a4/2...ew-questions-1/
http://everything2.com/title/hard%2520inte...w%2520questions

Говорю сразу, я ответы не смотрел да и нет их еще на русском, а мой английский не тот)... в любом случае, пытаемся ответить сами!

Сообщение отредактировано: compiler - 5.06.2008 21:46

[мисс_граффити]

про первую задачу.
допустим, у нас 5 гномов.
им надели колпаки и построили в такой ряд:
ч ч б ч б
то есть
1 1 0 1 0
последний гном считает
1 xor 1 xor 0 xor 1 = 1
говорит: черный
его убивают (не повезло).

предпоследний получает такую задачу:
1 xor 1 xor 0 xor х = 1
(х - его шляпа. цвет неизвестен ему)
находит, что х=1 (черный).

третий гном:
1 xor 1 xor х xor 1 = 1
находит, что х=0

так же поступают оставшиеся гномы

[compiler]

про первую задачу...

спасибо.. понял..