Задачка про визирей

← →
jack128 © (2005-01-23 17:49) [0]

Падишах решил, что у него слишком много визирей. Позвал их и говорит - решил я от части визирей избавиться. Завтра утром вас выстроят в очередь затылок в затылок и наденут каждому по колпаку. Часть колпаков будет чёрная, часть белая (сколько каких неизвестно). Каждый будет видеть колпаки впереди стоящих, но не будет видеть свой колпак и колпаки позади себя. Дальше, начиная с конца очереди каждый назовёт цвет. Если назовёт цвет своего колпака - останется визирем, если не угадает - потеряет голову.
Но визири за ночь придумали способ, при котором погибнет максимум один визирь.

PS: Если один визирь говорит, все остальные слышат.
PS2: Затылок в затылок - значит лицом к затылку впереди стоящего.

← →
Antonn © (2005-01-23 17:52) [1]

jack128 © (23.01.05 17:49)
первый назовет цвет полпака второго(второй услышит), и, возможно, не угадает свой. Аминь.

← →
Antonn © (2005-01-23 17:53) [2]

в догонку: и так далее :)

← →
jack128 © (2005-01-23 18:00) [3]

Antonn © (23.01.05 17:53) [2]
в догонку: и так далее :)
Куда далее? Допустим у первого черный калпак, у второго белый, у третьего черный. Первый говорит "белый калпак" и отдает богу душу. А что должен сказать второой, чтобы и самому выжить и третьего не похоронить? ;-)

← →
KilkennyCat © (2005-01-23 18:04) [4]

они играли интонациями. Говорящий говорит радостно: белый! это означает, что впереди него - два белых. Если говорит грустно... белый... значит, впереди - белый, черный.

← →
KilkennyCat © (2005-01-23 18:07) [5]

кроме того, он мог передать и больше информации, если говорил так:
у меня белый колпак,
у меня колпак белый,
на мне белый колпак и т.д.

← →
Kerk © (2005-01-23 18:08) [6]

Если колпаки следующих двух совпадают, первый говорит - "белый колпак", иначе - "черный". Затем, следующий видя колпак впереди называет свой. И третий тоже. :)

← →
Antonn © (2005-01-23 18:10) [7]

я, вообще то, солидарен с падишахом - перестрелять таких визерей надо.

← →
KilkennyCat © (2005-01-23 18:10) [8]

> Kerk © (23.01.05 18:08) [6]

а четвертый?

← →
Kerk © (2005-01-23 18:17) [9]

Первый смотрит каких колпаков больше и, если колпак следующего принадлежит к большей группе, говорим - "белый", иначе - "черный". А дальше включается теорвер. :)

← →
KilkennyCat © (2005-01-23 18:20) [10]

Вообще-то, если визирей не очень много, то первый может назвать все колпаки сразу, если палач немного протормозит:

"падишах, ты:
сволочь, добрый, урод, красивый, приятный..." и т.д. положительное определение - белый, отрицательное - черный.

← →
jack128 © (2005-01-23 18:20) [11]

KilkennyCat © (23.01.05 18:07) [5]
хе, у мя тоже такая мысль была. Нет, не интанациями, ни чем другим дополнительную информацию передовать нельзя.

← →
Zeqfreed © (2005-01-23 18:21) [12]

6
5
4
3
2
1

2-ый скажет "белый" если колпаки 2-ого и 4-ого одинаковы. 2-ой и 3-тий теперь знают какой у 2-ого колпак. Дальше если 1-ый сказал "белый" и у 4-ого белый колпак то *совпадение* будет "белым", а *несовпадение* - "черным", если же у 4-ого черный, то *совпадение* - "черный", а *несовпадение* - белый. Теперь 3-ий знает, что значат "белый" и "черный" в словах 2-ого. Теперь второй смотрит, если колпаки 3-его и 5-ого одинаковы, он говорит *совпадение*, иначе *не совпадение*. И так далее.

Вроде объяснил не очень понятно, но разобраться наверно можно )

← →
default © (2005-01-23 18:22) [13]

jack128 © (23.01.05 17:49)
тривиальность
последний, к примеру, называет(уславливаются об этом заранее)
белый цвет если число белых колпаков чётно и чёрный если нечётно
он всё равно не знает свой цвет
следующий по погибели/выживанию определяет истинную чётность белых колпаков и зная общее количество визирей определяет число красных колпаков
по тому что он видит впереди и слышал сзади и зная чётность белых шаров каждый точно определяет свой цвет

← →
Zeqfreed © (2005-01-23 18:23) [14]

В самом начале "1-ый скажет...".. опечаточка

← →
Kerk © (2005-01-23 18:23) [15]

Zeqfreed © (23.01.05 18:21) [12]

так много народу поубивают, надо убить одного.

← →
Kerk © (2005-01-23 18:24) [16]

> белый цвет если число белых колпаков чётно и чёрный
> если нечётно

Блин! Ну я почти догадался.. :))) см [9]
Жаль...

← →
Zeqfreed © (2005-01-23 18:25) [17]

число красных колпаков
чётность белых шаров
Че-то я даже слов не могу подобрать )
Это ты вообще откуда взял?

← →
Antonn © (2005-01-23 18:25) [18]

> к много народу поубивают, надо убить одного.

падишаха

← →
Kerk © (2005-01-23 18:25) [19]

Zeqfreed © (23.01.05 18:25) [17]

ЛОЛ !!! :)

← →
Zeqfreed © (2005-01-23 18:26) [20]

Kerk © (23.01.05 18:23) [15]
Не, по моим рассчетом только одного убьют... может я объяснил коряво, ну или ошибся.

← →
jack128 © (2005-01-23 18:28) [21]

default © (23.01.05 18:22) [13]
тривиальность

Ну куда нам до вас, до великих :-)
Я залез в булеву алгебру и через неё вывел эквивалентное решение..

← →
default © (2005-01-23 18:29) [22]

jack128 © (23.01.05 18:28) [21]
не просто после той пятничной задачки эта уже...

← →
Zeqfreed © (2005-01-23 18:31) [23]

А все-таки про белые шары и красные колпаки мне объясните, тупому?

← →
default © (2005-01-23 18:31) [24]

Zeqfreed © (23.01.05 18:25) [17]
теорвером клинит...гы

← →
jack128 © (2005-01-23 18:32) [25]

Zeqfreed © (23.01.05 18:21) [12]
второй смотрит, если колпаки 3-его и 5-ого одинаковы, он говорит *совпадение*, иначе *не совпадение*.
второй не может говорить *совпадение* или *не совпадение*. Он ДОЛЖЕН сказать цвет своего колпака

default © (23.01.05 18:29) [22]
не просто после той пятничной задачки эта уже...
А-а. А я что то пропустил эту задачку..

← →
default © (2005-01-23 18:35) [26]

jack128 © (23.01.05 18:32) [25]
там посмотри ещё нерешённая осталась с сортировкой того же порядка вроде
отсортировать за время O(N) массив содержащий какую-то перестановку целых чисел 0..N-1
точнее можно в ветке которая щас где-то внизу посмотреть

← →
Zeqfreed © (2005-01-23 18:35) [27]

jack128 © (23.01.05 18:32) [25]
ДА! Он скажет цвет СВОЕГО колпака, а следующий за ним будет расценивать его как *совпадение* или *не совпадение*

← →
KilkennyCat © (2005-01-23 18:37) [28]

> default © (23.01.05 18:35) [26]

ты же вроде решил ее? я даже собирался вникнуть..

вот
1. Дан массив, содержащий некоторую перестановку чисел 0.. N-1
Отсортировать его за О(N) операций и с O(1) доп. памяти.
решение типа for i := 0 to High(DynArray) do DynArray[i] := i не подходит надо в массиве переставлять как-то

default © (23.01.05 18:38) [29]
А линк не дашь на эти задачки?? Что то поиск молчит..

Zeqfreed © (23.01.05 18:35) [27]
ДА! Он скажет цвет СВОЕГО колпака, а следующий за ним будет расценивать его как *совпадение* или *не совпадение
Ты не понимаешь. Вот, например, у второго - белый колпак, а у 3-его и пятого они разного цвета, что второй должен говорить??

и все-таки, использование дополнительной информации более экономично :)

А вот если усложнить задачу, добавив возможность ошибки:
Предположим, что где-то в середине один из визирей хватается за сердце (прибегает придворный лекарь, вау-вау, разряд, еще разряд! мы теряем его! ом-мани-падме-хум...) и не успевает сказать ни слова. Будет ли прерван (искажен)поток информации, и если да, то как надо сделать, чтобы не исказился?

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

Проблема только в том что я не знаю не противоречит ли это условию задачи.

jack128 © (23.01.05 18:53) [31]
http://delphimaster.net/view/14-1106272166/
ну это не первоисточник где была та задача, тот, наверно, сабж ушёл в архив
SergP © (23.01.05 20:09) [34]
в условии только про цвет сказано

KilkennyCat © (23.01.05 19:02) [32]
исказится
ситуация будет как в начале
придётся следующему за тем кого шибануло указывать чётность белых шаров(ну или нечётность и не обязательно белых...)

> default © (23.01.05 20:24) [38]

да, но он ведь слышал всю предыдущую информацию. Можно ли высчитать вероятность восстановления (угадывания) информации, или она все-таки становится нулевой?

KilkennyCat © (23.01.05 20:27) [39]
да, но тот "нестабильный элемент" оборвал цепь
и всё начинается заново
шансы же следующего за нестабильным - 50/50
кстати мне почему-то кажется тут ещё может какие-то решения есть...

Задачка про визирей Найти похожие ветки