Rezolvare PBinfo #4179

Î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.

Cerința

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:

barliga.in

2 10
3 7 5 10
4 1 5 10 2

barliga.out

9
1 1

Explicație

Există două scânduri, pe fiecare dintre ele fiind scrise numerele naturale de la 1 la 10. Pe scândura 1 sunt scrise pe fața roșie 3 valori (7, 5, 10), celelalte 7 valori fiind scrise pe fața galbenă (1, 2, 3, 4, 6, 8, 9). Pe scândura 2 sunt scrise pe fața roșie 4 valori (1, 5, 10, 2), celelalte 6 valori fiind scrise pe fața galbenă (3, 4, 6, 7, 8, 9). Punctajul maxim care se poate obține este 9.

O modalitate prin care obținem punctajul maxim este de a întoarce cu fața galbenă în sus scândura cu numărul 1. Vor deveni astfel vizibile numerele 1, 2, 3, 4, 6, 8, 9 pe scândura 1 și rămân vizibile numerele 1, 2, 5, 10 pe scândura 2, în total 9 numere distincte.