| Про визирей |
Автор: Василий Захаров (---.ornet.ru)
Дата: 25-07-03 01:52
Вот вам ещё одна "программистская" задачка. В чём-то похожа на предыдущую, но решается вроде как по-другому. Кто знает - сразу не колитесь, дайте людям подумать пару дней. :)
У некоего султана было 100 визирей. И однажды показалось ему, что все они глупые и ничего не понимают, и решил он их проверить. Вызвал всех и объяснил суть проверки - султан строит всех визирей в цепочку, случайным образом, одного в затылок другому, потом проходит вдоль цепочки и каждому на голову надевает колпак одного из трёх цветов - синий, красный или зелёный. Потом подходит к каждому начиная с последнего (того, у которого за спиной никого нет) и спрашивает, какого цвета колпак у того на голове. Если визирь отвечает верно - он признаётся умным и остаётся в живых, если ошибается - ему рубят голову.
Сразу уточняю:
- колпаки есть только этих трёх цветов
- каждому визирю достаётся строго и ровно один колпак
- колпаки раздаются совершенно случайным образом
- количество колпаков каждого цвета произвольное,
одних может быть больше, других - меньше
- каждый визирь в цепочке видит всех, кто стоит впереди него
(и колпаки у них на головах), и слышит, что отвечают
на вопрос те, кто стоит у него за спиной. Ну, вопли казнимых
он наверное тоже слышит (хотя для решения задачи это неважно,
но остроты придаёт :).
- каждый визирь отвечает на вопрос ровно одним словом,
"синий", "красный" или "зелёный". Больше никто ни с кем
не разговаривает.
В общем, объяснил султан визирям, что им грозит, и дал им ночь на совместное размышление. Сидели визири, думали, и почти сразу придумали алгоритм, при котором выживает примерно треть из них. Потом, уже к полуночи придумали алгоритм, при котором гарантированно выживает половина, а скорее всего даже две трети. Но и этот результат их, очевидно, не очень порадовал. :) В общем, они стали думать дальше и под утро нашли ещё более правильный путь. Чего и вам желаю. :)
|
|
| Темы |
Автор |
Дата |
|
Karamel-ka |
23-07-03 22:04 |
|
Karamel-ka |
23-07-03 23:39 |
|
Karamel-ka |
23-07-03 23:46 |
|
Василий Захаров |
24-07-03 01:11 |
|
Karamel-ka |
24-07-03 09:18 |
|
Пух |
24-07-03 09:21 |
|
Karamel-ka |
24-07-03 09:24 |
|
Pavel |
24-07-03 10:25 |
|
Karamel-ka |
24-07-03 10:34 |
|
Пух |
24-07-03 11:41 |
|
Пух |
24-07-03 11:44 |
|
Колесников Вячеслав |
24-07-03 21:11 |
|
Karamel-ka |
24-07-03 11:46 |
|
Must_die |
24-07-03 11:47 |
|
Must_die |
24-07-03 11:52 |
|
Alexey |
24-07-03 12:04 |
|
Karamel-ka |
24-07-03 12:14 |
|
Alexey |
24-07-03 12:20 |
|
Alexey |
24-07-03 12:33 |
|
Karamel-ka |
24-07-03 12:42 |
|
Karamel-ka |
24-07-03 12:46 |
|
Женя |
24-07-03 13:09 |
|
Karamel-ka |
24-07-03 13:13 |
|
Must_die |
24-07-03 13:39 |
|
Enigma |
24-07-03 17:53 |
|
Капитанская дочка |
24-07-03 13:20 |
|
Karamel-ka |
24-07-03 13:42 |
|
Must_die |
24-07-03 13:45 |
|
Karamel-ka |
24-07-03 13:50 |
|
Alexey |
24-07-03 13:52 |
|
Must_die |
24-07-03 13:56 |
|
Enigma |
24-07-03 14:23 |
|
Karamel-ka |
24-07-03 13:55 |
|
Alexey |
24-07-03 13:58 |
|
Karamel-ka |
24-07-03 14:01 |
|
Alexey |
24-07-03 14:05 |
|
Пух |
24-07-03 14:17 |
|
Karamel-ka |
24-07-03 14:24 |
|
Alexey |
24-07-03 14:25 |
|
Karamel-ka |
24-07-03 14:28 |
|
Alexey |
24-07-03 14:34 |
|
Alexey |
24-07-03 14:49 |
|
Пух |
24-07-03 14:55 |
|
Пух |
24-07-03 15:00 |
|
NCC |
24-07-03 17:46 |
|
Пух |
24-07-03 15:07 |
|
Karamel-ka |
24-07-03 15:09 |
|
Alexey |
24-07-03 15:41 |
|
зритель |
24-07-03 16:14 |
|
Karamel-ka |
24-07-03 16:17 |
|
зритель |
24-07-03 16:20 |
|
зритель |
24-07-03 16:24 |
|
зритель |
24-07-03 16:48 |
|
Karamel-ka |
24-07-03 18:02 |
|
Капитанская дочка |
24-07-03 18:06 |
|
зритель |
24-07-03 18:16 |
|
Василий Захаров |
24-07-03 18:18 |
|
зритель |
24-07-03 18:25 |
|
Enigma |
24-07-03 18:26 |
|
Василий Захаров |
24-07-03 18:29 |
|
зритель |
24-07-03 18:41 |
|
зритель |
24-07-03 18:44 |
|
Капитанская дочка |
24-07-03 20:15 |
|
Must_die |
24-07-03 20:19 |
|
зритель |
24-07-03 20:47 |
|
Must_die |
24-07-03 23:13 |
|
ЛЯП |
25-07-03 00:54 |
|
Василий Захаров |
25-07-03 01:31 |
|
Enigma |
25-07-03 12:53 |
|
Василий Захаров |
25-07-03 01:52 |
|
ЛЯП |
25-07-03 02:11 |
|
Капитанская дочка |
25-07-03 02:34 |
|
Василий Захаров |
25-07-03 02:51 |
|
Ал |
25-07-03 08:29 |
|
Пух |
25-07-03 09:41 |
|
Karamel-ka |
25-07-03 10:03 |
|
Капитанская дочка |
25-07-03 11:59 |
|
Белка |
25-07-03 13:13 |
|
Karamel-ka |
25-07-03 13:18 |
|
kfb |
25-07-03 13:42 |
|
Пух |
25-07-03 14:11 |
|
Капитанская дочка |
25-07-03 14:40 |
|
Василий Захаров |
25-07-03 14:12 |
|
Enigma |
25-07-03 16:47 |
|
Enigma |
25-07-03 16:48 |
|
Пух |
25-07-03 15:10 |
|
Капитанская дочка |
25-07-03 15:35 |
|
Пух |
25-07-03 15:47 |
|
Капитанская дочка |
25-07-03 16:07 |
|
Деза |
25-07-03 16:04 |
|
Деза |
25-07-03 16:07 |
|
Пух |
25-07-03 16:26 |
|
Капитанская дочка |
26-07-03 13:48 |
|
Колесников Вячеслав |
27-07-03 00:14 |
|
Колесников Вячеслав |
27-07-03 00:15 |
|
Колесников Вячеслав |
27-07-03 00:16 |
|
зритель |
25-07-03 17:40 |
|
Василий Захаров |
25-07-03 17:50 |
|
зритель |
25-07-03 20:53 |
|
Деза |
25-07-03 23:55 |
|
Ал |
26-07-03 00:22 |
|
Bagira |
26-07-03 03:33 |
|
Василий Захаров |
26-07-03 09:04 |
|
Белка |
26-07-03 13:45 |
|
Ал |
26-07-03 14:02 |
|
Деза |
26-07-03 20:00 |
|
зритель |
26-07-03 20:35 |
|
Василий Захаров |
26-07-03 21:27 |
|
Василий Захаров |
26-07-03 21:27 |
|
Bagira |
27-07-03 02:49 |
|
Василий Захаров |
27-07-03 06:18 |
|
Ал |
27-07-03 21:49 |
|
Василий Захаров |
27-07-03 22:29 |
|
Колесников Вячеслав |
28-07-03 01:31 |
|
Bagira |
28-07-03 01:50 |
|
Bagira |
28-07-03 02:49 |
|
Колесников Вячеслав |
28-07-03 06:44 |
|
Ал |
28-07-03 10:32 |
|
Пух |
28-07-03 09:13 |
|
Капитанская дочка |
28-07-03 12:31 |
|
Василий Захаров |
28-07-03 12:28 |
|
Василий Захаров |
28-07-03 12:41 |
|
Madre |
28-07-03 13:30 |
|
Деза |
28-07-03 13:34 |
|
Pavel |
28-07-03 14:01 |
|
Деза |
28-07-03 14:08 |
|
Деза |
28-07-03 14:11 |
|
Капитанская дочка |
28-07-03 14:13 |
|
Деза |
28-07-03 14:21 |
|
Пух |
28-07-03 15:38 |
|
Василий Захаров |
28-07-03 15:43 |
|
ЛЯП |
28-07-03 16:10 |
|
Деза |
28-07-03 16:41 |
|
Guest |
28-07-03 21:40 |
|
Пух |
28-07-03 16:45 |
|
Karamel-ka |
28-07-03 16:56 |
|
Пух |
28-07-03 16:58 |
|
Пух |
28-07-03 17:07 |
|
Karamel-ka |
28-07-03 17:11 |
|
Пух |
28-07-03 17:19 |
|
ЛЯП |
28-07-03 17:44 |
|
Karamel-ka |
28-07-03 17:48 |
|
ЛЯП |
29-07-03 01:28 |
|
Пух |
28-07-03 17:49 |
|
Karamel-ka |
28-07-03 17:55 |
|
Деза |
28-07-03 21:45 |
|
Деза |
28-07-03 22:16 |
|
Василий Захаров |
28-07-03 23:30 |
|
Бородатый |
29-07-03 06:11 |
|
Колесников Вячеслав |
29-07-03 06:45 |
|
Бородатый |
29-07-03 06:30 |
|
Василий Захаров |
29-07-03 11:14 |
|
Капитанская дочка |
29-07-03 16:22 |
|
Пух |
29-07-03 17:49 |
|
Василий Захаров |
30-07-03 00:15 |
|
Bagira |
30-07-03 00:31 |
|
Василий Захаров |
30-07-03 00:48 |
|
Karamel-ka |
30-07-03 14:31 |
|
Bagira |
30-07-03 14:36 |
|
Karamel-ka |
30-07-03 14:45 |
|
Bagira |
30-07-03 14:55 |
|
Ал |
30-07-03 15:00 |
|
Василий Захаров |
30-07-03 15:05 |
|
Karamel-ka |
30-07-03 15:10 |
|
Bagira |
30-07-03 15:10 |
|
Karamel-ka |
30-07-03 15:12 |
|
Василий Захаров |
30-07-03 15:19 |
|
Alexey |
30-07-03 15:27 |
|
Alexey |
30-07-03 15:43 |
|
Alexey |
30-07-03 15:49 |
|
Василий Захаров |
30-07-03 15:53 |
|
Василий Захаров |
30-07-03 15:57 |
|
Василий Захаров |
30-07-03 16:05 |
|
ЛЯП |
30-07-03 16:05 |
|
Василий Захаров |
30-07-03 16:09 |
|
Ал |
30-07-03 16:17 |
|
Василий Захаров |
30-07-03 16:23 |
|
Ал |
30-07-03 17:12 |
|
Капитанская дочка |
30-07-03 17:15 |
|
Василий Захаров |
30-07-03 17:24 |
|
Капитанская дочка |
30-07-03 17:25 |
|
Nataly |
30-07-03 17:56 |
|
Nataly |
30-07-03 17:57 |
|
Nataly |
30-07-03 17:57 |
|
Капитанская дочка |
30-07-03 17:30 |
|
Ирина |
30-07-03 18:07 |
|
Василий Захаров |
05-08-03 13:27 |
