LINUX.ORG.RU
ФорумTalks

Ещё задачки на сообразительность


0

0

Навеяно предыдущими топиками. А давайте поделимся, кто какие знает, только не те в которых нужно долго рассуждать, а где есть короткий правильный ответ.

По слухам с собеседования в микрософте: Есть группа людей. На наих надевают красные и синие шапки. Суть игры заключается в том, что каждого, по очереди спрашивают какого цвета на нём шапка. Если человек ощибаются, его убивают. Перед игрой всем дают время сговориться, потом ведут в комнату, гдё начинают спрашивать.

Как выбрать стратегию называния цвета, чтобы минимизировать количество смертей?

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

Ответ на: комментарий от Lumi

>Есть две крайние точки у решения. 1 человек болеет = 30 дней, 29 человек болеет = 30 дней. Это явно максимумы. Минимум будет посередине.

Ну примените это рассуждение к моему примеру с 8 человеками.

Низачет.

PS есть ли у кого знакомые программисты из yandex-а Может кто нибудь откроет страшную тайну, как доказывается оптимальность (ну или есть ли более оптимальное решение, кроме того рекурсивного)

ival ★★
()
Ответ на: комментарий от ival

> Ну примените это рассуждение к моему примеру с 8 человеками.

Болеют по одному = 8 дней. Болеют по 7 = 8 дней. Ты привёл пример для 4 из восьми, получил 6 дней. 6 дней явно меньше, чем 8, то есть болеть по 4 более оптимально. Что не так?

> Низачет.

А если подумать?

Lumi ★★★★★
()
Ответ на: комментарий от ival

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

in_dance
() автор топика
Ответ на: комментарий от in_dance

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

Это позволяет отделить хомо сапиенсов от хомо зубретикус.

Lumi ★★★★★
()
Ответ на: комментарий от Lumi

>4 5, >5 6, >8 7... двоичный логарифм эн квадрат.

Ну да. С той стратегией, что я описывал дней нужно.

2*<округленное вверх до ближайшего целого log_2(n)>

А почему меньше нельзя?

ival ★★
()
Ответ на: комментарий от ival

Я там выше рассматривсл решение когда болеют или ходят по одному. это два максимума по краям. сколько ожидается минимумов?

Lumi ★★★★★
()
Ответ на: комментарий от ival

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

Lumi ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.