http://acm.pku.edu.cn/JudgeOnline/problem?id=1176

   Задача: Лампы для праздника

   Для освещения заключительного вечера IOI'98 имеется N цветных ламп, пронумерованных от 1 до N. Четыре кнопки позволяют управлять лампам следующим образом:

   - кнопка 1 - когда эта кнопка нажата, все лампы изменяют свое состояние: те, что были включены, становятся выключенными, те, что были выключены - включаются;
   - кнопка 2 - изменяет состояние всех ламп, имеющих нечетные номера;
   - кнопка 3 - изменяет состояние всех ламп, имеющих четные номера;
   - кнопка 4 - изменяет состояние всех ламп, имеющих номера, вычисляемые по формуле 3k + 1 (где k >= 0), т.е. 1, 4, 7, ...

   Имеется счетчик С, который учитывает (хранит) суммарное число нажатий всех кнопок.

   В начале вечера все лампы были включены, а счетчик С равен нулю.

   Задано значение счетчика С и информация о конечном состоянии некоторых ламп. Напишите программу для определения всех различных возможных конечных (окончательных) конфигураций N ламп, чтобы каждая конфигурация соответствовала заданной информации.

   Входные данные

   Входные данные состоят из четырех строк, задающих количество ламп N, конечное значение счетчика С и состояние некоторых ламп в окончательной конфигурации.

   В первой строке содержится число N, во второй строке - конечное значение счетчика С. Третья строка содержит список номеров ламп, о которых известно, что в конечной конфигурации они включены. Третья строка содержит список номеров ламп, о которых известно, что они включены. Номера ламп в строке отделены друг от друга одним пробелом, и список заканчивается числом -1. Четвертая строка содержит список номеров ламп, о которых известно, что в окончательной конфигурации они выключены. Номера ламп в строке отделены друг от друга одним пробелом, и список заканчивается числом -1.

   Параметры N и С ограничены: 10 <= N <= 100, 1 <= C <= 10000.
   Количество ламп, о которых известно, что в конечной конфигурации они включены, меньше или равно 2. Количество ламп, о которых известно, что в конечной конфигурации они выключены, меньше или равно 2.

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

   Каждая строка содержит N символов, где первый символ представляет состояние лампы номер 1, а последний символ представляет состояние лампы N. 0 (нуль) означает, что лампа выключена, а 1 (единица) означает, что лампа включена.

   Пример входных данных

10
1
-1
7 -1

   Пример выходных данных

0000000000
0101010101
0110110110

   Обсуждение идеи решения

   Решение на С++:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define MAXLAMP	6
#define LAMPMASK	((1<<MAXLAMP)-1)

int nlamp;
int nswitch;
int ison;
int known;

int poss[1<<MAXLAMP];

int flip[4] = {
    LAMPMASK,/* flip all lights */
    LAMPMASK & 0xAA, 	/* flip odd lights */
    LAMPMASK & 0x55,	/* flip even lights */
    LAMPMASK & ((1<<(MAXLAMP-1))|(1<<(MAXLAMP-4)))	/* lights 1, 4 */
};

/*
 * Starting with current light state ``lights'', flip exactly n switches
 * with number >= i.
 */
void
search(int lights, int i, int n)
{
    if(n == 0) {
	if((lights & known) == ison)
	    poss[lights] = 1;
	return;
    }

    for(; i<4; i++)
	search(lights ^ flip[i], i+1, n-1);
}

void
printseq(FILE *fout, int lights)
{
    int i;
    char s[100+1];

    for(i=0; i<nlamp; i++)
	s[i] = (lights & (1<<(MAXLAMP-1 - i%MAXLAMP))) ? '1' : '0';
    s[nlamp] = '\0';
    fprintf(fout, "%s\n", s);
}

int main(void){
    FILE *fin, *fout;
    int a, i, impossible;

    fin = stdin;
    fout = stdout;
    assert(fin != NULL && fout != NULL);

    fscanf(fin, "%d %d", &nlamp, &nswitch);

    for(;;) {
	fscanf(fin, "%d", &a);
	if(a == -1)
	    break;
	a = MAXLAMP-1 - (a-1) % MAXLAMP;
	ison |= 1<<a;
	known |= 1<<a;
    }

    for(;;) {
	fscanf(fin, "%d", &a);
	if(a == -1)
	    break;
	a = MAXLAMP-1 - (a-1) % MAXLAMP;
	assert((ison & (1<<a)) == 0);
	known |= 1<<a;
    }

    if(nswitch > 4)
	if(nswitch%2 == 0)
	    nswitch = 4;
	else
	    nswitch = 3;

    for(; nswitch >= 0; nswitch -= 2)
	    search(LAMPMASK, 0, nswitch);

    impossible = 1;
    for(i=0; i<(1<<MAXLAMP); i++) {
	if(poss[i]) {
	    printseq(fout, i);
	    impossible = 0;
	}
    }
    if(impossible)
	fprintf(fout, "IMPOSSIBLE\n");

    exit(0);
}