Apagant els llums P37448

Les classes del professor Oak són una barreja d’exemples dibuixats a la pissarra i de codis picats amb dos dits i mostrats amb el projector. Per poder fer aquestes classes, cal que el pobre estudiant més proper als interruptors vagi apagant i encenent els llums de l’aula.

Fins aquí la història és real, ara comença la ficció. Hi ha n llums i m interruptors. Els operaris de la FME han barrejat els cables, i ara cada interruptor canvia l’estat (d’encès a apagat, o d’apagat a encès) de diversos llums alhora. Donat l’estat inicial de cada llum, i els llums canviats per cada interruptor, de quantes maneres es poden apagar tots els llums? Com que prémer el mateix interruptor dues vegades seria com no fer res, cada interruptor es pot pitjar com a molt un cop.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n, seguida dels estats inicials dels n llums en ordre (un 0 indica apagat, un 1 indica encès), seguits de m, seguida de la informació dels m interruptors: Per a cadascun, tenim el nombre f de llums als quals afecta, seguit de f nombres diferents entre 0 i n−1. Suposeu 1 ≤ n ≤ 100, 1 ≤ m ≤ 15, i 1 ≤ f ≤ n.

Sortida

Per a cada cas, escriviu quantes combinacions dels interruptors apaguen tots els llums.

Pista

La solució esperada és un backtracking senzill.