Le croissant saboteur P87011


Statement
 

pdf   zip

thehtml

Enguany, n equips van participar al SWERC, amb un total d’m problemes per resoldre. Aquesta competició la guanya l’equip que resol estrictament més problemes que la resta. (Realment hi ha un sistema de desempat, però en aquest problema l’ignorem.) Tanmateix, en Lucien, el black croissant hacker més famós de París, també era l’entrenador d’un dels equips que van participar, i va sabotejar la competició per intentar guanyar.

En Lucien, que sabia quins problemes resoldria cada equip, va aconseguir infiltrar-se al jutge per sabotejar alguns problemes, que així no podrien ser resolts per cap equip. Tanmateix, per evitar alarmar els organitzadors del SWERC, en Lucien va decidir no sabotejar més de k ‍problemes. Amb aquesta informació, podeu determinar si en Lucien va poder fer que el seu equip guanyés?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n, m i k, seguits d’n files amb m caràcters cadascuna. El j-èsim caràcter de la i-èsima fila és 1 si l’equip i és capaç de resoldre el problema j, i 0 altrament. L’equip d’en Lucien sempre és el de la primera fila. Poseu suposar 2 ≤ n ≤ 25, 2 ≤ m ≤ 25, i 0 ≤ km.

Sortida

Per a cada cas, escriviu “OUI” si l’equip d’en Lucien va poder guanyar el SWERC, i “NON” altrament.

Pista

La solució esperada d’aquest problema és un backtracking bastant optimitzat.

Public test cases
  • Input

    2 2 0
    10
    01
    
    2 2 1
    10
    01
    
    2 2 2
    10
    01
    
    5 12 3
    100010000011
    000010110110
    101001100010
    001100001011
    110010011000
    
    5 12 4
    100010000011
    000010110110
    101001100010
    001100001011
    110010011000
    

    Output

    NON
    OUI
    OUI
    NON
    OUI
    
  • Information
    Author
    Jan Olivetti
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++