Apagando las luces P37448


Statement
 

pdf   zip

html

Las clases del professor Oak son una mezcla de ejemplos dibujados en la pizarra y de códigos tecleados con dos dedos y mostrados con el proyector. Para poder hacer estas clases, el pobre estudiante más cercano a los interruptores tiene que ir apagando y encendiendo las luces del aula.

Hasta aquí la historia es real, ahora empieza la ficción. Hay n luces y m interruptores. Los operarios de la FME han mezclado los cables, y ahora cada interruptor cambia el estado (de encendido a apagado, o de apagado a encendido) de diversas luces a la vez. Dado el estado inicial de cada luz, y las luces cambiadas por cada interruptor, ¿de cuantas maneras se pueden apagar todas las luces? Como pulsar el mismo interruptor dos veces sería como no hacer nada, cada interruptor se puede pulsar como mucho una vez.

Entrada

La entrada consiste en diversos casos, cada uno con n, seguida de los estados iniciales de las n luces en orden (un 0 indica apagada, un 1 indica encendida), seguidos de m, seguida de la información de los m interruptores: Para cada uno, tenemos el número f de luces a las cuales afecta, seguido de f números diferentes entre 0 y n−1. Suponed 1 ≤ n ≤ 100, 1 ≤ m ≤ 15, y 1 ≤ fn.

Salida

Para cada caso, escribid cuantas combinaciones de los interruptores apagan todas las luces.

Pista

La solución esperada és un backtracking sencillo.

Public test cases
  • Input

    1  1
    1
    1  0
    
    4  0 1 0 1
    3
    1  2
    2  1 3
    2  3 1
    
    1  0
    4
    1  0
    1  0
    1  0
    1  0
    
    2  0 1
    1
    2  1 0
    

    Output

    1
    2
    8
    0
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++