2171 - pluricex1

Cerința

Anul acesta se organizează prima ediție a Olimpiadei Pluridisciplinare pentru Centrele de Excelență, PluriCEX. Fiecare Centru de Excelență din țară va trimite la concurs o echipă formată din k membri (toți participanți la Centrul de Excelență). Echipa va trebui să rezolve probleme interdisciplinare, disciplinele vizate fiind cele de la Centrul de Excelenţă (D discipline, pe care le vom considera numerotate de la 1 la D). Directorul CEX Iași a făcut o listă cu primii n cei mai buni elevi de la CEX, apoi a numerotat elevii de la 1 la n, în ordinea apariției lor în listă. Pentru fiecare elev, directorul a notat disciplinele la care el participă la CEX. Scrieți un program care să determine toate echipele ce pot fi formate din k dintre cei n elevi de pe lista directorului, cu condiția ca pentru fiecare disciplină să existe în echipă cel puțin un membru care să studieze la CEX disciplina respectivă.

Date de intrare

Fișierul de intrare pluricex1.in conţine pe prima linie trei numere naturale n k D (cu semnificația din enunț). Urmează n linii care descriu participările la CEX ale celor n elevi de pe lista directorului. Mai exact, pe linia i+1 este descrisă participarea elevului i astfel: nr d1 d2 ... dnr. Primul număr de pe linie (nr) indică numărul de discipline la care participă elevul i. Următoarele nr numere reprezintă disciplinele la care participă elevul i. Numerele scrise pe aceeași linie sunt separate prin spațiu.

Date de ieșire

Fișierul de ieșire pluricex1.out va conţine toate echipele ce se pot forma respectând condiţiile din enunţ, câte o echipă pe o linie. Membrii unei echipe vor fi scrişi în ordine crescătoare, separaţi prin câte un spaţiu. Echipele vor fi scrise în ordine lexicografică.

Restricții și precizări

• 0 < n ≤ 22
• 0 < k ≤ 8
• 0 < D ≤ 10
• Pentru datele de test problema admite întotdeauna soluţie, numărul de soluţii fiind mai mic de 20000.
• Spunem că vectorul (x1, x2, ..., xn) precedă lexicografic vectorul (y1, y2, ..., yn) dacă există un indice i astfel încât xj=yj, pentru orice 1 ≤ j < i, iar xi < yi.

Exemplu 1

Intrare

6 3 5
1 2
2 1 4
3 2 4 3
1 5
2 3 1
1 3

Iesire

2 3 4
3 4 5

Rezolvare

<syntaxhighlight lang="python" line> def generate_teams(n, k, d, participations):

   from itertools import combinations

   teams = []

   for comb in combinations(range(1, n + 1), k):
       valid = True
       disciplines = [0] * d

       for student in comb:
           for discipline in participations[student - 1]:
               disciplines[discipline - 1] += 1

       if all(disciplines):
           teams.append(comb)

   return sorted(teams)

def read_input(input_file):

   with open(input_file, 'r') as file:
       n, k, d = map(int, file.readline().strip().split())
       participations = []

       for _ in range(n):
           line = list(map(int, file.readline().strip().split()))
           participations.append(line[1:])

   return n, k, d, participations

def write_output(output_file, teams):

   with open(output_file, 'w') as file:
       for team in teams:
           file.write(' '.join(map(str, team)) + '\n')

def main():

   input_file = 'pluricex1.in'
   output_file = 'pluricex1.out'

   # Citim datele de intrare
   n, k, d, participations = read_input(input_file)

   # Generăm echipele valide
   teams = generate_teams(n, k, d, participations)

   # Scriem rezultatele în fișierul de ieșire
   write_output(output_file, teams)

if __name__ == "__main__":

   main()

</syntaxhighlight>