4179 - barliga

Cerința

În așteptarea marii confruntări cu turcii, oștenii moldoveni își antrenează mintea, jucând un joc de echipă denumit Bârligă. O echipă are N jucători, numerotați de la 1 la N, în ordinea în care sunt așezați. Fiecare jucător primește o scândură vopsită pe o față cu roşu, iar pe cealaltă cu galben. Pe fiecare scândură sunt scrise toate numerele naturale de la 1 la V, fiecare număr o singură dată; unele numere sunt scrise pe fața roșie, celelalte sunt scrise pe fața galbenă a scândurii. La începutul jocului, toate scândurile sunt așezate cu faţa roșie în sus. Când primul jucător strigă “Bârligă!” fiecare jucător din echipă poate decide dacă să lase scândura sa cu fața roșie în sus sau să o întoarcă (să o “bârlige”) cu fața galbenă în sus. Punctajul obținut de echipă este egal cu numărul de valori distincte vizibile la final. Scrieți un program care cunoscând N, numărul de jucători din echipă, precum și valorile scrise pe fața roșie a scândurii primite de fiecare jucător, determină punctajul maxim pe care îl poate obține echipa, precum și numerele de ordine ale jucătorilor care trebuie să întoarcă scândura cu față galbenă în sus, pentru a obține acest punctaj maxim.

Date de intrare

Fișierul de intrare barliga.in conține pe prima linie numerele naturale N și V, cu semnificația din enunț. Pe următoarele N linii se află informațiile despre scândurile celor N jucători, în ordinea de la 1 la N. Linia care descrie o scândură are forma nr r1 r2 … rnr, cu semnificația: pe fața roșie a scândurii sunt scrise nr numere naturale distincte cuprinse între 1 și V, acestea fiind r1, r2, …, rnr.

Date de ieșire

În fișierul de ieșire barliga.out se va scrie pe prima linie un număr natural reprezentând punctajul maxim pe care îl poate obține echipa. Pe cea de a doua linie va fi scris un număr natural T, reprezentând numărul de jucători care trebuie să întoarcă scândura cu fața galbenă în sus, urmat de T numere naturale distincte cuprinse între 1 și N, reprezentând numerele de ordine ale jucătorilor care trebuie să întoarcă scândura cu fața galbenă în sus.

Restricții și precizări

• 2 ≤ N ≤ 16
• 3 ≤ V ≤ 80.000
• Valorile aflate pe aceeași linie în fișierul de intrare, respectiv în fișierul de ieșire sunt separate printr-un singur spațiu.
• Dacă există mai multe soluții pentru ca echipa să obțină punctaj maxim, se va afișa oricare dintre acestea.
• Punctajul pe test se obține dacă sunt afișate corect atât punctajul maxim, cât și o modalitate de obținere a punctajului maxim.

Exemplu 1

Intrare

2 10
3 7 5 10
4 1 5 10 2

Iesire

9
1 1

Rezolvare

<syntaxhighlight lang="python" line> import itertools

def main():

   # Citirea datelor de intrare
   with open("barliga.in", "r") as fin:
       N, V = map(int, fin.readline().split())
       red_boards = []
       yellow_boards = []

       for _ in range(N):
           data = list(map(int, fin.readline().split()))
           red_boards.append(set(data[1:]))
           # Vom genera yellow_boards ca fiind complementul numerelor de pe fața roșie
           yellow_boards.append(set(range(1, V+1)) - red_boards[-1])

   max_score = 0
   best_combination = []

   # Verificăm toate combinațiile posibile de întoarcere a scândurilor
   for flip_combination in itertools.product([False, True], repeat=N):
       visible_numbers = set()
       current_combination = []

       for i in range(N):
           if flip_combination[i]:
               visible_numbers.update(yellow_boards[i])
               current_combination.append(i + 1)
           else:
               visible_numbers.update(red_boards[i])

       if len(visible_numbers) > max_score:
           max_score = len(visible_numbers)
           best_combination = current_combination

   # Scrierea rezultatului în fișierul de ieșire
   with open("barliga.out", "w") as fout:
       fout.write(str(max_score) + "\n")
       fout.write(str(len(best_combination)) + " " + " ".join(map(str, best_combination)) + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>