copii2

Copii2

== include(page="template/taskheader" task_id="copii2") ==

Poveste şi cerinţă...

În Gheorgheni sunt $N$ copii pasionaţi de fotbal, pe care o să îi numerotăm cu numere naturale de la $1$ la $N$. Ei doresc să alcătuiască $T{~1~}$ echipe, unde $T{~1~}$ nu poate depăşi o valoare maximă $K$, astfel încât fiecare echipă va disputa câte un meci împotriva fiecăreia dintre celelelate $T{~1~}-1$ echipe. Astfel, în această etapă au loc <tex> \frac{T_{1} (T_{1} -1)}{2} </tex>  meciuri. După ce se termină toate aceste meciuri, copiii pot hotarî să se reîmpartă în $T{~2~}$ $(T{~2~} &le; K)$ echipe şi să dispute o nouă etapă de meciuri. Scopul final este ca după terminarea tuturor etapelor, fiecare copil să fi avut cel puţin odată ca adversar pe fiecare dintre ceilalţi copii.
 
h2. Cerinţă
 
Determinaţi numărul minim de etape care trebuie disputate astfel încât fiecare copil să fi avut ca adversar cel puţin o dată pe fiecare dintre ceilalţi copii. De asemenea, afişaţi o modalitate de alcătuire a echipelor în fiecare dintre aceste etape.

h2. Date de intrare

Fişierul de intrare $copii2.in$ ...

Fişierul de intrare $copii2.in$ conţine pe prima linie $N$ şi $K$, reprezentând numărul de copii şi numărul maxim de echipe care pot fi alcătuite într-o rundă.

h2. Date de ieşire

În fişierul de ieşire $copii2.out$ ...

Pe prima linie a fişierului $copii2.out$ se va afişa numărul minim de runde, $R$. Pentru fiecare rundă $i$ $(1 ≤ i ≤ R)$ se va afişa: pe prima linie numărul de echipe $T{~i~}$ şi pe următoarele $T{~i~}$ linii se va afişa componenţa echipelor. A j-a dintre aceste linii $(1 ≤ j ≤ T{~i~})$ va avea următorul format:
 
$      K{~j~}  C{~j~}[ 1 ]  C{~j~}[ 2 ]  ...  C{~j~}[ K{~j~} ]$
 
unde $K{~j~}$ reprezintă numărul de copii din echipa $j$, iar $C{~j~}[ 1 ], C{~j~}[ 2 ], ... C{~j~}[ K{~j~} ]$ reprezintă numerele asociate copiilor din echipa $j$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 100.000$
* $2 ≤ K ≤ N$
* Un copil nu poate face parte din două echipe în aceeaşi etapă.
* Nu este obligatoriu ca echipele alcătuite într-o etapă să aibă acelaşi număr de copii.
* Doi copii sunt adversari dacă fac parte din echipe diferite
* Pentru $5%$ din teste $K = N$
* Pentru $30%$ din teste $K = 2$
* Pentru afişarea corectă a numărului de runde se acordă $20%$ din punctaj
* La o anumită rundă pot exista copii care să nu facă parte din nicio echipă.

h2. Exemplu
table(example). |_. copii2.in |_. copii2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

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

|
h3. Explicaţie

...

Sunt $5$ copii care pot alcătui într-o etapă maxim $3$ echipe
În prima etapă copiii alcătuiesc trei echipe: una formată din copiii numerotati cu $1$ si $2$, a doua formată din copiii cu numerele de ordine $3$ şi $5$ şi a treia formată dintr-un singur copil $–$ cel numerotat cu $4$.
În a doua etapă ei alcătuiesc două echipe: una formată din copiii numerotaţi cu $1$ şi $5$ iar cealaltă din doi copiii – cei cu numerele $2$ si $3$.
 

== include(page="template/taskfooter" task_id="copii2") ==

5543