2109 - Dineu

Enunț

La un dineu participă reprezentanţii mai multor state. Fiecare reprezentant cunoaşte un număr de limbi străine. Doi reprezentanţi vor putea discuta direct dacă există cel puţin o limbă pe care o înţeleg amândoi. Organizatorii dineului doresc să existe cel puţin o masă la care să nu fie nevoie de translator, astfel oricare două persoane care stau la această masă să se înţeleagă direct.

Cerința

Cunoscând N – numărul de reprezentanţi, identificăm fiecare reprezentant cu un număr natural cuprins între 1 şi N, L – numărul limbilor străine care se vorbesc la dineu (acestea sunt codificate prin numerele naturale de la 1 la L), numărul de limbi vorbite de fiecare reprezentant şi codurile acestora să se determine numărul maxim de persoane care pot sta la o masa fără translator.

Date de intrare

Fişierul de intrare dineuIN.txt conţine, pe prima linie, numerele naturale N şi L, separate printr-un spaţiu, cu semnificaţia de mai sus. Pe fiecare dintre următoarele N linii se află informaţii despre câte un reprezentant, în ordinea numerelor de identificare a acestora. Astfel, pe linia corespunzătoare reprezentantului i (1≤i≤N), se află un număr natural nri- numărul limbilor străine vorbite de acesta, urmat de nri numere naturale distincte l1 l2 ... lnri, reprezentând codurile acestora. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieşire dineuOUT.txt va conţine două linii. Pe prima linie se află numărul maxim de reprezentanţi care stau la aceeaşi masă. Pe a doua linie se află numerele de identificare ale acestora. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 1 <= N <= 20

• 1 <= L <= 10

• 1 <= nri, l1, l2, ..., lnri <= 10

• Dacă există mai multe soluţii se va afişa cea mai mică din punct de vedere lexicografic

Exemplul 1:

dineuIN.txt

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

dineuOUT.txt

4
1 2 3 4

Explicație

1 cu 2 vorbesc în limba 3

1 cu 4 vorbesc în limba 5

1 cu 3 vorbesc în limba 1

2 cu 4 vorbesc în limba 4

2 cu 3 vorbesc în limba 4

3 cu 4 vorbesc în limba 4

există şi alte soluţii, de exemplu soluţia 1 2 3 5, dar este mai mare din punct de vedere lexicografic

Exemplul 1:

dineuIN.txt

21 5
3 1 3 5 
2 3 4
3 1 2 4
2 4 5
2 2 3

dineuOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verificare_restrictii(n, l, limbi):

   if not (1 <= n <= 20) or not (1 <= l <= 10):
       return False

   for i in range(1, n + 1):
       k = sum(limbi[i])
       if not (1 <= k <= 10):
           return False

   return True

def main():

   nMAX = 20
   lMAX = 10

   # Deschide fișierele pentru citire și scriere
   with open("dineuIN.txt", "r") as fin, open("dineuOUT.txt", "w") as fout:
       try:
           n, l = map(int, fin.readline().split())
       except ValueError:
           fout.write("Datele nu corespund restrictiilor impuse")
           return

       limbi = [[0] * (lMAX + 1) for _ in range(nMAX + 1)]

       for i in range(1, n + 1):
           try:
               data = list(map(int, fin.readline().split()))

               # Verifică dacă linia citită conține suficiente elemente
               if len(data) < 2:
                   fout.write("Datele nu corespund restrictiilor impuse")
                   return

               k = data[0]
               for j in range(1, k + 1):
                   if j < len(data):
                       limbi[i][data[j]] = 1
                   else:
                       fout.write("Datele nu corespund restrictiilor impuse")
                       return
           except ValueError:
               fout.write("Datele nu corespund restrictiilor impuse")
               return

       # Verifică restricțiile
       if not verificare_restrictii(n, l, limbi):
           fout.write("Datele nu corespund restrictiilor impuse")
           return

       dp = [0] * (1 << nMAX)
       solmax = []

       dp[0] = 1
       for mask in range(1, (1 << n)):
           i = 0
           while not (mask & 1 << i):
               i += 1

           oldmask = mask ^ 1 << i
           if dp[oldmask]:
               okkk = True
               for j in range(n):
                   if oldmask & 1 << j:
                       ok = False
                       for k in range(1, l + 1):
                           if limbi[j + 1][k] and limbi[i + 1][k]:
                               ok = True
                               break

                       if not ok:
                           okkk = False
                           break

               dp[mask] = okkk

           if dp[mask]:
               sz = bin(mask).count('1')

               if sz == len(solmax):
                   ok = False
                   k = 0
                   for j in range(n):
                       if mask & 1 << j:
                           if ok:
                               solmax[k] = j + 1
                           else:
                               if j + 1 < solmax[k]:
                                   solmax[k] = j + 1
                                   ok = True
                               elif j + 1 > solmax[k]:
                                   break
                           k += 1

               elif sz > len(solmax):
                   solmax = [j + 1 for j in range(n) if mask & 1 << j]

       # Scrie rezultatele în fișierul de ieșire
       fout.write(f"{len(solmax)}\n")
       fout.write(" ".join(map(str, solmax)))

if __name__ == "__main__":

   main()

</syntaxhighlight>