Ответ на задачу про монеты сегодня с утра пришел сразу же. Привожу ниже. А
Димыч пусть уж комментирует, так
ли было у ребят с Хабра, если ему не лень, конечно.
Как и раньше буду писать "0", когда монета повернута аверсом и "1", когда она
повернута реверсом. Если обозначить развороты пары монет A, B, то под операцией "^"
буду понимать A^B=0, когда сумма чисел A+B - четная и A^B=1 - в противном случае.
Для тех, кто знает, что это, операция "^" - это XOR.
Пример: 1^0^1^1^0 = 1, т.к. 1+0+1+1+0=3 - нечетное число.
Начнем со случая, когда доска имеет размеры 2х2. Исходную выкладку монет запишем след.
образом:
A B
C D
Предлагается такой код: номер строчки с "магической" монетой определяется значением A^C: например,
первая строка когда A^C=0 и вторая строка, когда A^C=1. Номер столбца
будет определяться так же значением A^B (т.е. первый столбец, когда A^B=0 и второй когда A^B=1).
Покажем, что такой код позволит всегда указать на "магическую" монету, перевернув не более одной
монеты в исходной раскладке.
Действительно, в исходной раскладке могут быть следующие варианты:
1) В принятом коде раскладка уже указывает на "магическую" монету — ничего не переворачиваем.
2) В принятом коде раскладка указывает на правильную строку и неправильный столбец — переворачиваем монету B,
меняя тем самым A^B и сохраняя A^С
3) В принятом коде раскладка указывает на неправильную строку и правильный столбец — переворачиваем монету С,
меняя тем самым A^C и сохраняя A^B
4) И строка и столбец в исходной раскладке неправильные — переворачиваем монету A и меняем сразу и A^C и A^B.
Пример (звездочкой помечена "магическая" монета):
10
01*
раскладка кодирует положение (1,1). Ничего не переворачиваем.
Еще пример:
11*
11
Раскладка кодирует положение (1,1). У нас неправильный столбец. Переворачиваем монету в положении (1,2) (она же в этом случае "магическая").
И еще пример:
1 1
1 1*
Раскладка кодирует положение (1,1), а "магическая" монета в положении (2,2), т.е. и строка и столбец — неправильные. Переворачиваем
монету в положении (1,1).
Переходим к случаю 4x4. Пусть раскладка имеем вид:
A11 B11 A12 B12
C11 D11 C12 D12
A21 B21 A22 B22
C21 D21 C22 D22
Алгоритм следующий:
1) Посчитать:
A11^B11^C11^D11 A12^B12^C12^D12
A21^B21^C21^D21 A22^B22^C22^D22
2) Пользуясь кодировкой для случая 2х2, определить блок, в котором следует перевернуть монету.
3) Посчитать (пока ничего не переворачивали):
A11^A12^A21^A22 B11^B12^B21^B22
C11^C12^C21^C22 D11^D12^D21^D22
4) Пользуясь кодировкой для случая 2x2, определить элемент, который следует повернуть (блок уже знаем).
Пример:
1 1 0 1
0 1 1 1
1 0 1* 0
1 1 1 1
Считаем четности:
1 1
1 1
Значит переворачивать нужно монету в блоке (1,1).
Снова считаем четности:
1 0
1 0
Нужно перевернуть монету в положении (1,2) блока (1,1), т.е. монету в положении (1,2).
Приходим к раскладке:
1 0 0 1
0 1 1 1
1 0 1* 0
1 1 1 1
Чтобы угадать "магическую" монету опять считаем четности:
0 1
1 1
По нашему коду "магическая" монета находится в блоке (2,2).
И опять считаем четности:
1 1
1 0
По нашему коду, "магическая" монета находится в положении (1,1) блока (2,2), т.е. в положении (3,3), что совпадает с загаданным.
Можно проверить очень легко, что это будет работать в любом случае (следует из свойств операции "^" и того как считались четности).
Обобщение на полный случай 8x8 легко произвести, но этапов подсчета четностей будет уже 4, а не 2.
Писать еще больше мне уже лень
