Эрудиция и смекалка

[IlyaTIP]

Стратегии 50 и 66 уже всяко разжевали и пояснили, нет, опять особое мнение...

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

[Марья-2]

Марья-2, Вы уже знали этот ответ или только что его придумали?

Нет, не знала. Получила огромное удовольствие от решения красивой задачи. Спасибо.

[olc0267]

Нет, не знала. Получила огромное удовольствие от решения красивой задачи. Спасибо.

А мне всё-таки непонятно. Сократим число мудрецов до 6.
Как будут выглядеть вычисления для ряда 1-2-2-0-1-0 ?

[Марья-2]

Кажется, начинаю понимать. Надо суммировать ВСЕ впереди стоящие числа? Но за одну минуту (60 сек.) сложить 100 чисел нереально. А кричать надо каждую минуту.

Напоминаю, что можно не подсчитывать всю сумму, а складывать только остатки по модулю 3 (т.е. складывать в троичной системе счисления, отбрасывая все цифры, кроме последней).
Вот правила сложения:
0+0=0
0+1=1
0+2=2
1+0=1
1+1=2
1+2=0
2+0=0
2+1=0
2+2=1
Не так уж и сложно для мудрецов

[olc0267]

Вот правила сложения:
0+0=0
0+1=1
0+2=2
1+0=1
1+1=2
1+2=0
2+0=0
2+1=0
2+2=1
Не так уж и сложно для мудрецов

Допустим. Возьмём такой ряд 0-1-2-2-2-0-1-1-0-2-1-2-1-1-0

1-й. р(1)=1 (правильно 0, казнили)
2-й p(2)=0 (3+1-0)/3=1 (1)
3-й р(3)=2 (6+1-1-2)/3=1 (1)
4-й р(4)=0 (6+? -1-0)/3

Какое число надо поставить вместо знака вопроса? 2-й мудрец вычислил остаток 0. Но кричал-то он 1! А что он там вычислил - четвёртый не знает. Если он поставит 1, как кричал 2-й, то он не угадает. Он может угадать, если второй крикнет правильный остаток - 0. Но второй не может крикнуть 0, потому что его казнят.

[Марья-2]

Как будут выглядеть вычисления для ряда 1-2-2-0-1-0 ?

Предположим, что крайний слева (1) - это "первый" - тот, кто видит всех и первым отвечает.
Итак:
p1 = 2+2+0+1+0 = 2
p2 = 2+0+1+0 = 0
p3 = 0+1+0 = 1
p4 = 1+0 = 1
p5 = 0 = 0
Первый ("смертник") говорит "синий!". Это он сигнализирует остальным, что сумма передних
(s2+s3+...s6) = 2 (p1)
У второго сумма впереди стоящих s3+s4+...+s6 = 0, а сумма вместе с ним = s2+s3+...s6 =2. (Т.е. после того, как к 0 был добавлен его
собственный цвет, получилось 2). очевидно, что его цвет 2-0 = 2. Он кричит "синий!" (2).
ВСЕ остальные отнимают 2 от суммы p1(=2), озвученной первым. То есть
s3+s4+...+s6 = (p1 -s2) = 2 - 2 = 0
У третьего сумма передних s4+s5+s6 = 1, а сумма вместе с ним s3+s4+...+s6= 0. Очевидно, что цвет третьего - 2 (0-1=2). Когда он озвучивает цвет 2,
все остальные отнимают 2 от суммы, полученной на предыдущем этапе (0).
s4+s5+s6 = (p1 -s2 - s3) = 0 - 2 = 1.
У четвертого сумма передних s5+s6 = 1, а сумма вместе с ним - s4+s5+s6 = 1. 1 - 1 =0, т.е. цвет четвертого- 0 . После того, как он крикнул "белый",
Остальные отнимают 0 от суммы, полученной на предыдущем этапе (1).
s5+s6 = (p1 -s2 - s3 - s4) = 1 - 0 = 1.
У пятого сумма передних s6 =0, а сумма вместе с ним 1. Очевидно, что его цвет 1 - 0 = 1. После озвучки остальные (в данном случае остался только шестой) отнимают его от суммы, полученной на предыдущем этапе (1).
s6 = (p1 -s2 - s3 - s4 - s5) = 1 - 1 = 0. Это и есть цвет шестого.
Уф

[olc0267]

Да, красиво. У меня для такой задачки не только тактовой частоты, но и глубины стека не хватает. Но тогда почему же не спасётся последний? Спасутся 99+1/3 человек, потому что первого есть шанс тупо угадать.

А суть в том, что нужно просчитать не только то, что видишь, но и то что слышишь. Тогда будешь знать не только то, что крикнул предыдущий мудрец, но и то, что он вычислил. И тогда для твоих собственных вычислений информации вполне достаточно.

[Марья-2]

Последний тоже спасется, это мы уже выяснили Это у меня под конец ЦП сбойнул

[GORLAB]

Впрочем, выяснили - хороший случай -3 трупа. Плохой случай - 50 трупов. Всё зависит от расстановки и соотношения цветов колпаков.

Любителям формул напоминаю условие- Выкрикивает каждый только Один цвет!!! И если надо между своим цветом или подсказкой в ответе на цвет впереди стоящего, то что вы считаете каждый из них крикнет? Арифметически -всё равно +1 труп. Т.е. в подсказке либо спасёт впередистоящего, гибнет сам или себя спасает, но губит впередистоящего неверным ответом.

[alvadep]

Видео:

Без обид.