Editing 2109 - Dineu (section)

= Exemplul 1: =
<code>dineuIN.txt</code>
 5 5
 3 1 3 5 
 2 3 4
 3 1 2 4
 2 4 5
 2 2 3
<code>dineuOUT.txt</code>
 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: ==
<code>dineuIN.txt</code>
 21 5
 3 1 3 5 
 2 3 4
 3 1 2 4
 2 4 5
 2 2 3
<code>dineuOUT.txt</code>
 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>