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

← →
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]

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

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

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

← →
default © (2005-01-23 18:38) [30]

KilkennyCat © (23.01.05 18:37) [28]
да и MBo тоже, интересно было бы его решение посмотреть

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

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

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

← →
KilkennyCat © (2005-01-23 19:02) [32]

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

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

← →
Zeqfreed © (2005-01-23 19:23) [33]

jack128 © (23.01.05 18:53) [31]

Блин, вроде получалось, когда до этого считал... ну да ладно, кажись ошибся )

← →
SergP © (2005-01-23 20:09) [34]

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

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

← →
SergP © (2005-01-23 20:16) [35]

> [13] default © (23.01.05 18:22)

Хм.. Только что заметил что уже решено... Извиняюсь...

← →
default © (2005-01-23 20:16) [36]

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

← →
default © (2005-01-23 20:18) [37]

SergP © (23.01.05 20:16) [35]
задача [29] не решена

← →
default © (2005-01-23 20:24) [38]

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

← →
KilkennyCat © (2005-01-23 20:27) [39]

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

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

← →
default © (2005-01-23 20:31) [40]

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

← →
default © (2005-01-23 20:33) [41]

KilkennyCat © (23.01.05 20:27) [39]
хотя вдруг в послед-ти колпаков(названных и которые впереди) следующему за нестабильным удастся узрить какую-то закономерность или хотя бы вероятностно он всё-таки может прикинуть...

← →
GuAV © (2005-01-23 20:35) [42]

default © (23.01.05 20:33) [41]

Но если он прикинет, и скажет что прикинул, а не четность, он же не восстановит связь.

← →
default © (2005-01-23 20:37) [43]

GuAV © (23.01.05 20:35) [42]
да и другого подведёт точнее других!

← →
KilkennyCat © (2005-01-23 20:38) [44]

но с другой стороны, он владеет гораздо большей информацией, чем первый. Неужели эта информация абсолютно бесполезна?

← →
марсианин © (2005-01-23 20:44) [45]

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

торможу я.. ничего не понимаю..
чтоб погиб максимум 1 визирь уже 2-ой должен гарантировано знать СВОЙ цвет?? как он его узнает? ведь первый прокричит только четно ли число белых.

может, пример приведете?

> [29] default © (23.01.05 18:38)
> 1. Дан массив, содержащий некоторую перестановку чисел 0..N-1
> Отсортировать его за О(N) операций и с O(1) доп. памяти.

тоже не понимаю.. ведь это рядовая задача сортировки. быстрая сортировка требует O(n*log n) операций, а нам чего, нужно изобрести алгоритм СУПЕР-сортировки???

← →
марсианин © (2005-01-23 20:52) [46]

про визирей дошло :о)

← →
default © (2005-01-23 21:02) [47]

KilkennyCat © (23.01.05 20:38) [44]
допустим колпаки распределены так:
123456789
ЧББЧБЧЧБЧ

последний визирь (девятый) считает впереди себя белые колпаки и
видит что их 4 то есть чётное количество и произносит белый цвет как
раз это означающий правда сам откидывается поскольку у него колпак чёрный
следующий теперь знает истинную чётность белых колпаков - их действительно чётное число
зная что последний на белом цвете откинулся - значит у него чёрный и видя впереди себя три
белых колпака он смекает что у него белый цвет поскольку их чётное число
седьмой знает что сзади один белый колпак, а спереди три белых - значит у него чёрный
и вдруг 6 откидывается!пятый знает что сзади был один белый колпак точно и может ещё шестой -
но это точно неизвестно
он видит что впереди его два белых колпака, то есть либо у него белый а у шестого чёрный или
наоборот обе ситуации равновероятны и ситуация повторяется с элемента 5 так как бы он был
последним в последовательности визирев
он может конечно гадать, НО он тогда подставит под удар совизирей

← →
default © (2005-01-23 21:03) [48]

марсианин © (23.01.05 20:44) [45]
я тоже опешил на счёт сортировки!

← →
марсианин © (2005-01-23 21:15) [49]

[47] default ©
> зная что последний на белом цвете откинулся

не.. какой цвет у последнего не имеет значения.. он, конечно, откинулся, но "отряд не заметил потери бойца" (с)
или, его могли не сразу :)

2-ой услышал из-за спины от 1-го "белый". это к примеру значит, что число белых четно(4).. а он видит нечетное (3) количество. значит, на репе у него белый.
3-ий видит 2 белых колпака, но помнит, что 1-ый перед смертью крикнул белый и перед ним назвали тоже белый.
значит, было четное число - 1 = нечетное.. а видит четное. значит у него тоже белый.. и т.п.
т.е. без вероятностей

← →
default © (2005-01-23 21:39) [50]

марсианин © (23.01.05 21:15) [49]
"не.. какой цвет у последнего не имеет значения.. он, конечно, откинулся, но "отряд не заметил потери бойца" (с)
или, его могли не сразу :)"
как это? если бы последний имел белый цвет то истинное число белых колпаков представилось бы предпоследнего визерю не нечётное и отсюда дальнейший ход другой

← →
default © (2005-01-23 21:40) [51]

блин, как это? если бы последний имел белый цвет то истинное число белых колпаков представилось бы предпоследнему визерю как нечётное и отсюда дальнейший ход другой

← →
марсианин © (2005-01-23 21:47) [52]

предпоследний последнего все равно не видит. каждый видит народ только перед собой. в т.ч. и последний.

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

марсианин © (23.01.05 21:47) [52]
"предпоследний последнего все равно не видит"
да
последний-то чётность указывает по тому что он впереди видит
после же того как он озвучит цвет предпоследний и все остальные визири отсюдла узнают ИСТИННУЮ чётность белых колпаков и в соответ-ии с этим значением, тем что они видят впереди себя и что слышали до себя они называют свой цвет когда до них дойдёт черёд
"цветность" последнего визиря важна!

← →
GEN++ © (2005-01-23 23:09) [54]

А по-моему все гораздо проще:
последний называет цвет впереди стоящего;
каждый следующий говорит:
a - если цвет впереди стоящего совпадает с его цветом,
то он называет цвет
б - если цвет впереди стоящего не совпадает с его цветом,
то он говорит "на мне не цвет"
пример:
б,б,ч,ч,x
5 на мне черный
4 на мне черный
3 на мне НЕ белый
2 на мне белый
таким образом каждый слышит название своего цвета

← →
марсианин © (2005-01-23 23:14) [55]

ну не нужно им знать "истинную четность"!

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

смотри, берем твою последовательность:
ЧББЧБЧЧБЧ 1-ый видит :ББЧБЧЧБЧ - четно кричит :белый 2-ой понял :четно видит :БЧБЧЧБЧ - нечетно кричит :белый! 3-ий понял : было четно и прокричали "белый" - нечетно видит : ЧБЧЧБЧ - четно кричит: белый! 4-ый понял : было четно и 2 раза прокричали "белый" - четно видит : БЧЧБЧ - четно кричит : черный! 5-ый понял : было четно и 2 раза прокричали "белый" - четно видит : ЧЧБЧ - нечетно кричит : белый!
и т.д.
видишь, про цвет первого никто не вспоминает.

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

GEN++ © (23.01.05 23:09) [54]
Внимательней читай ветку - подобный способ предложил KilkennyCat [4],[5]

← →
KilkennyCat © (2005-01-23 23:45) [57]

и еще вопросик, при пропаже одного визиря важна его позиция? может, в одном варианте информация невосстановима,а в другом - восстановима?

← →
GEN++ © (2005-01-23 23:51) [58]

>jack128 ©
>...Дальше, начиная с конца очереди каждый назовёт цвет

и ничен лишнего. В моем случае, если убрать слова "на мне" -
результат не изменится, а вот в KilkennyCat [4],[5]
результат может быть трагичным.

← →
KilkennyCat © (2005-01-24 00:11) [59]

> результат может быть трагичным.

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

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

Сработает старый вариант решения?

← →
jack128 © (2005-01-24 00:12) [60]

KilkennyCat © (23.01.05 23:45) [57]
и еще вопросик, при пропаже одного визиря важна его позиция? может, в одном варианте информация невосстановима,а в другом - восстановима?

Не-а. Информация в любом случае невостановима.

Подойдем к проблеме формально. Пусть a1, a2, a3... - цвета колпаков на визирях. b - тот цвет, который назвал последний визирь. Для решения исходной задачи нам нужна такая функция
f(x1, x2, ..., xn) = b , что при известных x1, x2, x3..x(k-1), x(k+1), x(k+2)..., b мы могли бы узнать значение xk. Пример такой функции привел default. Для решения задачи в помершим от сердечного приступа визирем нужно следующее: пусть приступ был у визиря xm значит функция должна быть такая, что при известных x1, x2, x(k-1), x(k+1),...x(m-1), x(m+1)..., b мы бы могли узнать xk Такое возможно только если f(x1, ..) НЕ зависит от xm. Но в таком случае мы не можем узнать какой колпак на этом визире(а это нам нужно, ведь мы же не знаем зарание какой именно визирь помрет зарание)...

← →
jack128 © (2005-01-24 00:13) [61]

jack128 © (24.01.05 0:12) [60]
Пусть a1, a2, a3... - цвета колпаков на визирях
имелось в виду Пусть x1, x2, x3... - цвета колпаков на визирях

← →
SergP © (2005-01-24 00:18) [62]

> Сработает старый вариант решения?

Конечно сработает...

← →
KilkennyCat © (2005-01-24 00:25) [63]

> Конечно сработает...

всегда говорит предпоследний, он никогда не знает свой цвет, и цвет стоящего позади него. После того, как он сказал, информация изменилась, так как последний стал первым. И снова должен говорить предпоследний, который опять не знает свой цвет, и цвет стоящего позади.

Или я ошибаюсь?

← →
kaif © (2005-01-24 00:25) [64]

правильный ответ

марсианин © (23.01.05 23:14) [55]

Самый последний рискует и кричит сумму по модулю 2 всего, что видит впереди. Если сумма черных колпаков четная, то кричит белый! Условились четную сумму черных назвать белым цветом. Он рискует. Если его казнили (это главная информация), то одним черным меньше - теперь черных нечетное число. Если не казнили - черных четное число. Истинная полная сумма уже известна. Все загибают палец на правой руке, если полная сумма четная, или разогнуть если нечетная. Теперь остается каждому посчитать свою сумму по впередистоящим, согнуть или разогнуть указательный палец на левой руке, в зависимости от того, сумма черных впереди него четная, или нет. А потом внимательно слушать, что кричат сзади. Если кричат черный - сгибать/разгибать указательный палец на правой руке. Когда очередь дошла до него сравнить состояние своих пальцев (XOR) и назвать цвет своего колпака. Если пальцы загнуты одинаково - белый, по-разному - черный.
Рискует лишь первый, который кричал.

← →
KilkennyCat © (2005-01-24 00:27) [65]

> Если его казнили (это главная информация),

разве это не избыточная информация, на уровне интонации и приставки "не" ?

← →
kaif © (2005-01-24 00:33) [66]

Инфомация вообще-то восстановима по-житейски. Допустим, кто-то хватил инфаркт. Его вынесут из очереди и все увидят, колпак на нем черный или белый. Если черный - те, за кем он стоял, должны поменять состояние указательного пальца правой руки на противоположное. Если же его никто не видит, то это повод для апелляцяции к процедуре. Можно потребовать, чтобы предъявили труп или хотя бы колпак. :) Я думаю, ситуация и так на грани - вряд ли султан будет возражать. Можно пригрозить оранжевой революцией.

← →
kaif © (2005-01-24 00:36) [67]

2 KilkennyCat ©
А я и не предлагаю использовать интонацию. Я за честное соблюдение правил. Интонация в данном случае не нужна. Все равно первый может пострадать и с жульничанием (передача информации интонацией) и без жульничания (алгоритм марсианина, реализацию я предложил с загибанием пальцев). Как раз жульничание - совершенно излишняя информация. Если бы я был султан и узнал бы, что они использовали алгоритм марсианина, я бы их всех наградил за смекалку. А если бы узнал, что они юзают интонационный принцип - я бы всех казнил, так как посчитал бы, что они все идиоты.

← →
SergP © (2005-01-24 00:36) [68]

> [63] KilkennyCat © (24.01.05 00:25)
>
> > Конечно сработает...
>
>
> всегда говорит предпоследний, он никогда не знает свой цвет,
> и цвет стоящего позади него. После того, как он сказал,
> информация изменилась, так как последний стал первым. И
> снова должен говорить предпоследний, который опять не знает
> свой цвет, и цвет стоящего позади.
>
> Или я ошибаюсь?

Я сначала не совсем понял условие...
Но вобще-то если пользоваться старым методом, то количество визирей которые могут попасть "под раздачу" увеличится с одного до двух.

← →
kaif © (2005-01-24 00:38) [69]

Если визирей может хватить инфаркт, то это не визири, а чмо какие-то. Их тогда всех надо почикать.

← →
kaif © (2005-01-24 00:40) [70]

ИМХО, несложная задачка. Я думал минуты две. Странно, что визири думали целую ночь. Нет, я бы все-таки их казнил за тупость.

> ИМХО, несложная задачка. Я думал минуты две. Странно, что
> визири думали целую ночь. Нет, я бы все-таки их казнил за
> тупость.

Это они от сильного перепуга так долго думали...

Вот и Путин не может от губернаторов избавиться. Нужно ему предложить этот метод. А губеранторам сказать, что на сайте мастеров дельфи за небольшие бабки ($50,000 на рыло) научат, как пальцы загибать. Матвиенку в хвост нужно поставить. Она женщина - ее не казнят. Правда тогда алгоритм может не сработать. Но оно и хорошо.

В случае с Путиным их можно не в очередь выстроить, а в верикаль. И не цвет колпаков называть, а цвет вышестоящей задницы. Начинает нижний.

Мораль в том, что будь ты хоть падишах - против визирей не попрешь.

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

> [73] kaif © (24.01.05 00:49)
> В случае с Путиным их можно не в очередь выстроить, а в
> верикаль. И не цвет колпаков называть, а цвет вышестоящей
> задницы.

Дык это что же, рубить голову тем кто не знает цвет вышестоящей задницы и оставлять тех кто знает?

> Дык это что же, рубить голову тем кто не знает цвет вышестоящей
> задницы и оставлять тех кто знает?

Ты просто не понял kaifa, он хочет рубить головы всем, а доп. условия - так, для "демократичности" :)

>default © (23.01.05 18:38) [30]
>да и MBo тоже, интересно было бы его решение посмотреть

твое решение лучше и наглядней.

procedure ReOrder(var a: array of Integer); var n, Start, SwapPos: Integer; begin n := Length(a); Start := 1; while true do begin SwapPos := Start; while true do begin if Odd(SwapPos) then SwapPos := n - 1 - (SwapPos div 2) else SwapPos := SwapPos div 2; if SwapPos = Start then Break; Swap(a[SwapPos], a[Start]); end; while a[Start] > a[Start - 1] do begin if Start = n div 2 then Exit; Inc(Start); end; end; end;

марсианин © (23.01.05 20:44) [45]

> [29] default © (23.01.05 18:38)
> 1. Дан массив, содержащий некоторую перестановку чисел 0..N-1
> Отсортировать его за О(N) операций и с O(1) доп. памяти.

>тоже не понимаю.. ведь это рядовая задача сортировки. быстрая >сортировка требует O(n*log n) операций, а нам чего, нужно >изобрести алгоритм СУПЕР-сортировки???

Сортировка произвольных данных действительно O(n*log n), но у нас есть очень важная информация о числах в массиве - то, что они не повторяются, представляют собой набор последовательных целых от 0 до n-1, т.е. для каждого элемента известно его место.

кстати задача [29] решима и достаточно просто особенно на фоне ветки в [36], но туда лучше не смотреть - нечестно!
kaif © (24.01.05 00:40) [70]
Вы решили задачу нарушив правила, пальцы загибать нельзя, тогда
уж проще чтобы каждый называл колпак впереди стоящему, просто делая паузы в ответе - тут заподозрить невозможно - мало-ли я думаю - перед смертью не надышишься как говорится...

MBo © (24.01.05 10:02) [81]
я тоже хотел это вариант проверить!переставлять я так стал с самого начала, но вот до определения следующего элемента Start дело не дошло, после своего варианта хотел и этот проверить, но не стал - всё равно времени лучше линейного в данной задаче быть не может...

Я даже вычислил фамилию последнего визиря. Это был Илларионов.

default © (24.01.05 10:10) [82]
кстати задача [29] решима и достаточно просто особенно на фоне ветки в [36], но туда лучше не смотреть - нечестно!
kaif © (24.01.05 00:40) [70]
Вы решили задачу нарушив правила, пальцы загибать нельзя

Я решал уже с расчетом продать идею губернаторам. Пальцы гнуть они умеют.

kaif © (24.01.05 00:25) [64]
...Если его казнили (это главная информация), то одним черным меньше - теперь черных нечетное число.

А как ты понял, что именно эта информация главная?

kaif © (24.01.05 00:25) [64]

И еще вопрос: почему, после того как этого черного убрали, паритет черных опять стал нечетным?

Собрал султан N своих мудрецов и поместил в темницу
сказал им: завтра вас выведут на площадь
поставят в колонну по 1 человеку
каждому на голову наденут колпак
одного из трех цветов - красный, зеленый, синий
причем стоящий сзади будет видеть цвета колпаков каждого стоящего впереди него
но не будет видеть цвета колпака тех, кто за ним и своего собственного
каждую минуту будут бить в гонг и при этом один мудрец должен сказать цвет колпака
если этот цвет совпадет с цветом его колпака - он останется в живых
если нет - ему отрубят голову
в случае молчания головы отрубят всем
(каждый раз цвет называет разный мудрец, разумеется)
мудрецы за ночь посовещались и придумали алгоритм
сколько мудрецов можно 100% спасти
нужно решение с максимум 1 потерянным мудрецом
трёхмерная вариация первой задачи, сложнее

default © (25.01.05 23:33) [90]
Так вроде то же решение, что и для "двумерной" задачи катит.
обозначим 0 - красный колпак, 1 - зеленый, 2 - синий. Первый визирь называет сумму колпаков по модулю 3. Каждый следующий исходя из услышанного и того, что он видит перед собой может назвать цвет своего колпака (его цвет = 3 - (сумма колпаков, которые он видит + плюс сумма того, что он слышал)...

jack128 © (26.01.05 0:35) [92]
его цвет = 3 - (сумма колпаков, которые он видит + плюс сумма того, что он слышал) mod 3
пора спать :)

jack128 © (26.01.05 00:54) [93]
что-то я не понял
какая сумма колпаков?если всех, то она известна заранее и получается никто не погибнет, а минимум 1 всегда может
если какого-то цвета, то ерунда получается

default © (26.01.05 8:27) [94]
блин, аналогии со своим же решением [13] не видишь? В твоем решении последний визирь называет сумму по модулю два, а у меня по модулю 3, вот и вся разница. C формулой я , возможно, действительно намудрил, вот программка иллюстрирующая алгоритм

//визири индексируются так, как они стоят в коллоне, а не так, как они говорят цвет своего колпака
procedure TForm1.Button1Click(Sender: TObject);
const
N = 50; // кол-во цветов
Count = 100; // кол-во визирей

function Check(Index: Integer; Arr: array of Integer): boolean;
var
i: Integer;
LSum, RSum: Integer;
begin
LSum := 0;
for i := low(Arr) to Index - 1 do
inc(LSum, Arr[i]);
// LSum - Сумма тех колпаков, которые он видит
RSum := 0;
for i := Index + 1 to high(Arr) - 1 do
inc(RSum, Arr[i]);
// LSum - Сумма тех колпаков, которые он слышал, за исключением последнего визиря, он называл не цвет своего колпака, а вычисленную величину
i := (LSum + RSum + Arr[Index]) mod N; // это то, что назвал последний визирь
i := i - (LSum + RSum) mod N;
if i < 0 then inc(i, N);
Result := i = Arr[Index];
end;

var
Visirs: array[0..Count - 1] of Integer;
i: Integer;
begin
for i := Low(Visirs) to high(Visirs) do
Visirs[i] := Random(N);
for i := low(Visirs) to high(Visirs) do
if not Check(i, Visirs) then
raise Exception.Create("Opps " + IntToStr(i));
end;

initialization
Randomize;

jack128 © (26.01.05 12:12) [95]
понятно
на счёт аналогии - я в первом варианте оперировал с чётностью, а не с остатком(хоть численно это одно и тоже) поэтому прямой аналогии нет тут

default © (26.01.05 12:35) [96]
я в первом варианте оперировал с чётностью, а не с остатком(хоть численно это одно и тоже)
А что такое четность числа?

jack128 © (26.01.05 12:39) [97]
я же писал в [96]
хоть численно они и равны прямой аналогии НЕТ!
это чистая психология!если бы я оперировал остатком то обобщение я бы тоже моментально сделал на любое число цветов, вот в чём дело

default © (26.01.05 12:42) [98]
чистая психология!
А. Ну это да.. Я нашел решение быстро, потому что решал исходную задачу через XOR, который тоже является суммой по модулю..

В условии не сказано, можно ли называть цвет колпака стоящего впереди. Значит можно 8)

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