Sadism P36909


Statement
 

pdf   zip

thehtml

(This problem was inspired by a nice sketch of a 2014 Christmas theater play at FME )

Consider n persons and m activities. For every person, we know the activities where he or she excels. Print all the ways to assign one activity to each person. All people must excel in their assigned activities, and no activity can be assigned more than once.

Input

Input consists in several cases. Every case begins with n and the names of the n persons in alphabetical order. Follow m, and the names of the m activities in alphabetical order. Finally, we have a matrix n × m, where at the column j of the row i we have a 1 if person i excels in j, and we have a 0 otherwise. You can assume 1 ≤ nm ≤ 10, and that there are no repeated words.

Output

For each case, print all the possible assignments. Inside every combination, persons must be sorted alphabetically. Combinations must be sorted lexicographically by activity. Print a line with 20 dots at the end of every combination, and a line with 30 dashes at the end of every case.

Public test cases
  • Input

    4 Enric Jordi Julia Salvador
    4 geocaching muntanyisme sadisme teatre
    0 1 0 0
    1 0 0 0
    0 0 0 1
    0 0 1 0
    
    2 Anna Ivet
    3 dormir jugar menjar
    1 1 0
    1 1 1
    

    Output

    Enric muntanyisme
    Jordi geocaching
    Julia teatre
    Salvador sadisme
    ....................
    ------------------------------
    Anna dormir
    Ivet jugar
    ....................
    Anna dormir
    Ivet menjar
    ....................
    Anna jugar
    Ivet dormir
    ....................
    Anna jugar
    Ivet menjar
    ....................
    ------------------------------
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++