Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 17
Мой ответ
Последний гном называет цвет шапки впередистоящего, при это 50%50 что он погибнет, предпоследний называет цвет своей шапки и точно выживает. Со следующей парой итерация повторяется. Тем самым при случайном распределении выжить может больше 70% гномов.
Написал, потом подумал и понял, что был неправ.
Спойлер
Примем белый цвет за 1, чёрный за 0. Последний гном ксорит(XOR) значения всех впереди стоящих и говорит его. Следующий ксорит всех впереди стоящих и предыдущий ответ, получая цвет своего колпака. Следующий опять ксорит всех впереди с предыдущими ответами. И так далее.
Таким образом все кроме одного выживут 100% и Последний с верояностью 50 %
Таким образом все кроме одного выживут 100% и Последний с верояностью 50 %
s/чёрный/синий
s/белый/красный
s/белый/красный
Вы уверены что алгоритм правильный?
Например для:
var a1 = 1 ^ 0 ^ 1 ^ 0 ^ 1 ^ 1;
var a2 = a1 ^ 0 ^ 1 ^ 0 ^ 1 ^ 1;
var a3 = a2 ^ 1 ^ 0 ^ 1 ^ 1;
var a4 = a3 ^ 0 ^ 1 ^ 1;
var a5 = a4 ^ 1 ^ 1;
var a6 = a5 ^ 1;
получим 010001, вместо ?01011.
var a1 = 1 ^ 0 ^ 1 ^ 0 ^ 1 ^ 1;
var a2 = a1 ^ 0 ^ 1 ^ 0 ^ 1 ^ 1;
var a3 = a2 ^ 1 ^ 0 ^ 1 ^ 1;
var a4 = a3 ^ 0 ^ 1 ^ 1;
var a5 = a4 ^ 1 ^ 1;
var a6 = a5 ^ 1;
получим 010001, вместо ?01011.
Да
Вы немного неправильно поняли суть.
Возьмём Вашу последовательность: 101011
Тогда алгоритм такой:
var a1 = 0 ^ 1 ^ 0 ^ 1 ^ 1; // 1
var a2 = a1 ^ 1 ^ 0 ^ 1 ^ 1; //0
var a3 = a1 ^ a2 ^ 0 ^ 1 ^ 1; //1
var a4 = a1 ^ a2 ^ a3 ^ 1 ^ 1; //0
var a5 = a1 ^ a2 ^ a3 ^ a4 ^ 1; //1
var a6 =a1 ^ a2 ^ a3 ^ a4 ^ a5; //1
Возьмём Вашу последовательность: 101011
Тогда алгоритм такой:
var a1 = 0 ^ 1 ^ 0 ^ 1 ^ 1; // 1
var a2 = a1 ^ 1 ^ 0 ^ 1 ^ 1; //0
var a3 = a1 ^ a2 ^ 0 ^ 1 ^ 1; //1
var a4 = a1 ^ a2 ^ a3 ^ 1 ^ 1; //0
var a5 = a1 ^ a2 ^ a3 ^ a4 ^ 1; //1
var a6 =a1 ^ a2 ^ a3 ^ a4 ^ a5; //1
Данные в задаче неполные, если троль сразу съедает неправильно ответивших, это даст дополнительную информацию впередистоящим.
Еще вариант
Гномы знают про операцию XOR, тогда гномы разбиваются на тройки, в каждой тройке последний гном говорит XOR цветов впередистоящих:
синий — синий = красный
синий — красный = синий
красный — синий = синий
красный — красный = красный,
В этом случае однозначно выживают двое впередистоящих. Из каждой тройки выживут точно двое, это уже 66%, и из оставшихся может выжить до половины, т.е. вполне может выжить 83% гномов.
синий — синий = красный
синий — красный = синий
красный — синий = синий
красный — красный = красный,
В этом случае однозначно выживают двое впередистоящих. Из каждой тройки выживут точно двое, это уже 66%, и из оставшихся может выжить до половины, т.е. вполне может выжить 83% гномов.
Вариант для гномов, которые не знают про операцию XOR.
Скрытый текст
В двух вариантах ответов можно зашифровать, например, «четный» и «нечетный». Далее, примем красный цвет равный 1, а синий будет 0. Первый гном суммирует цвета шапок всех остальных, используя этот код. И результат сообщает вслух (например, красный – «четный», «синий» — нечетный – у гномов есть вся ночь, чтобы договориться об этом).Отсюда.
Второй гном, услышав шифр, так же суммирует всех стоящих впереди. Если результат совпадает с тем, что сказал первый гном, значит цвет его шапки не повлиял на общую сумму. Стало быть, это «ноль» — синий. Если результат изменился, значит это «единица» — красный.
Третий и последующий гномы считают не только тех, кого видят впереди, но и ответы предыдущих гномов. И так же сравнивают результат с шифром самого первого гнома, вычисляя разницу (цвет своей шапки).
Этот способ позволяет выжить N-1 гному. Общее количество гномов при этом не имеет значения, задача решается для любого N. Самый первый гном не обязательно погибает: с вероятностью 50% шифр может совпасть с цветом его шапки и тогда он останется жив и здоров.
теперь такими постами на Хабре карму будут качать?
Характер гномиков является переменной в данной задачке?
Автор! Для Вас резко усложню задачу — шапочки трех цветов. Для упрощения — 100 гномиков. Сколько выживет?
Спасение n или n-1 гномов.
Скрытый текст
Каждый гном — это узел, который должен кроме того, что спасти себя, передать информацию следующим. Каким образом?
А таким, что впереди все будут слышать попытку стоящего сзади и также результат — выжил или нет.
Итак: первый гном считает разницу красных и синих шапочек, которые видит (их есть n-1 штук) и озвучивает остаток от деления сего числа на 2, кодируя его в цвет, соответствующий договоренности гномов, например, 0 — синий, 1 — красный, и либо выжывает, либо нет. НО зато следущший гном, услышав число и подсчитав количество гномов, которые есть перед ним и их цвета (а их уже n-2), сравнивает свой остаток с предыдущим и уже наверняка узнаёт, какой у него цвет. Далее все следующие гномы должны слышать, что говорят у них за спинами, и производить соответствующие вычисления в голове. Вуаля!
А таким, что впереди все будут слышать попытку стоящего сзади и также результат — выжил или нет.
Итак: первый гном считает разницу красных и синих шапочек, которые видит (их есть n-1 штук) и озвучивает остаток от деления сего числа на 2, кодируя его в цвет, соответствующий договоренности гномов, например, 0 — синий, 1 — красный, и либо выжывает, либо нет. НО зато следущший гном, услышав число и подсчитав количество гномов, которые есть перед ним и их цвета (а их уже n-2), сравнивает свой остаток с предыдущим и уже наверняка узнаёт, какой у него цвет. Далее все следующие гномы должны слышать, что говорят у них за спинами, и производить соответствующие вычисления в голове. Вуаля!
Вот еще одно усложнение задачи: число гномиков счетное(то есть гномики находятся в биективном соответствии с натуральными числами), спрашивается, можно ли спасти всех, кроме конечного числа гномиков.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Спасите гномиков от ужасного, но справедливого Троля