Fişierul intrare/ieşire:copii2.in, copii2.outSursăONI 2011 - Baraj
AutorMarius TibaAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test0.35 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Copii2

Î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ă T1 echipe, unde T1 nu poate depăşi o valoare maximă K, astfel încât fiecare echipă va disputa câte un meci împotriva fiecăreia dintre celelelate T1-1 echipe. Astfel, în această etapă au loc  \frac{T_{1} (T_{1} -1)}{2}  meciuri. După ce se termină toate aceste meciuri, copiii pot hotarî să se reîmpartă în T2 (T2 ≤ 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.

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.

Date de intrare

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

Date de ieşire

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 Ti şi pe următoarele Ti linii se va afişa componenţa echipelor. A j-a dintre aceste linii (1 ≤ j ≤ Ti) va avea următorul format:

  Kj Cj[ 1 ] Cj[ 2 ] ... Cj[ Kj ]

unde Kj reprezintă numărul de copii din echipa j, iar Cj[ 1 ], Cj[ 2 ], ... Cj[ Kj ] reprezintă numerele asociate copiilor din echipa j.

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

Exemplu

copii2.incopii2.out
5 3
2
3
2 1 2
2 3 5
1 4
2
2 1 5
2 3 2

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content