Хорошая задача, спасибо, приятно вечером после рабочей недели немного поразмышлять.
Ох-ох, ну, мне для решения математика всё же пригодилась, но, верю, кому-то будет достаточно просто очень хорошего воображения
Очень часто мне сложно понять как мыслят программисты, да и вообще любой человек, и, возможно, наоборот может быть верно тоже, поэтому я кратко опишу свой ход мыслей, а если будет кому-нибудь непонятно и интересно, то смогу более детально рассказать.
На мой взгляд задачу можно переформулировать попроще: представить раскраску вершин 64-мерного единичного куба в 64 цвета так, чтобы у любой вершины все её соседние вершины были разных цветов, это в предположении, что первый заключённый обязан перевернуть какую-нибудь монету, и заметим, что это более сложный случай, его и буду рассматривать.
В общем случае вершины n-мерного куба раскрасить в n цветов с таким условием нельзя, например, можете попытаться сделать такое перебором с обычным 3-мерным кубом. А вот с кубами размерности 2**n придумать такую раскраску можно, я отталкивался от естественной раскраски 4-мерного куба (смогу показать рисунок, если тут непонятно), надо добиться, чтобы изменение значения одной координаты вершины давало новый цвет. Другими словами если координаты вершины выписать в строку 2**n битов, то функция получения цвета вершины от изначальной с XOR от 2**k, где k от 0 до n-1, перебирала бы все n цветов, то есть была сюръективной. Если (2**n)-мерный куб представить как вытянутый по ещё одной оси уже раскрашенный (2**n - 1)-мерный куб, то изменение значения на этой последней координате не будет менять цвет, её можно исключить, а для остальных (2**n - 1) координат естественной функцией раскраски будет XOR от всех позиций(!) координат, где стоит единица. Для такой функции легко проверить выполнение требуемого свойства для раскраски вершин.
И, собственно, код для проверки моей идеи, надеюсь, что там всё достаточно очевидно. А если найдёте ошибку, то с меня подарок за ваше время и внимание.
Код:
#include <stdio.h>
#include <stdlib.h>
static unsigned int find_lsb_set(unsigned long long n)
{
unsigned int pos = 0;
if (!(n & 0xffffffff)) {
pos += 32;
n >>= 32;
}
if (!(n & 0xffff)) {
pos += 16;
n >>= 16;
}
if (!(n & 0xff)) {
pos += 8;
n >>= 8;
}
if (!(n & 0xf)) {
pos += 4;
n >>= 4;
}
if (!(n & 0x3)) {
pos += 2;
n >>= 2;
}
if (!(n & 0x1))
pos += 1;
return pos;
}
static unsigned int colour_decode(unsigned long long n) {
unsigned int pos, colour = 0;
/*
Get the same colour if MSB is flipped, it also ensures
that the resulting colour is in the expected range.
*/
n &= ~(1ULL << 63);
for (; n; n &= ~(1ULL << pos)) {
pos = find_lsb_set(n);
colour ^= (pos + 1);
}
return colour;
}
static int save_prisoners(unsigned long long board, unsigned int secret)
{
unsigned int colour, flip, guess;
/* Get an initial colour of the given configuration of coins */
colour = colour_decode(board);
/*
Select a cell to flip a coin to get the wanted colour of
the board, remember that flipping MSB does not change the colour.
*/
if (secret != colour)
flip = (colour ^ secret) - 1;
else
flip = 63;
/* Flip a coin on the selected cell */
board ^= (1ULL << flip);
/* Get a colour of the changed board */
guess = colour_decode(board);
printf("board: %016llx, secret: %02u --> "
"colour: %02u, flip: %02u, guess: %02u\n",
board, secret, colour, flip, guess);
return (secret == guess);
}
int main(int argc, char **argv) {
unsigned long long board;
unsigned int secret, i;
for (i = 0; i < 8; i++) {
srandom((1 << i) + i);
/* Represent a 8x8 board with coins as a (2**6)-bit number */
board = (unsigned long long)random() << 32 | random();
/* Encode a secret cell position as a 6-bit colour */
secret = random() & 0x3f;
/* Try to save prisoners */
if (save_prisoners(board, secret))
printf("Innocent people are saved.\n\n");
else
printf("Guileful villains are executed.\n\n");
}
return 0;
}
