12 aprilie. O zi istorica in evolutia umanitatii. In aceasta zi, in 1961, primul pamantean a ajuns in spatiul cosmic, efectuand o rotatie in jurul Pamantului. Au urmat altii, a urmat, in 1969, cucerirea primului corp ceresc altul decat Terra, Luna atat de admirata de indragostiti; au urmat Venus, Marte, apoi alte sisteme solare, alte corpuri ceresti.
Noile planete care indeplineau conditii de teraformare au fost transformate astfel incat sa poata fi populate.
In anul 8991, pe una din aceste planete a ajuns o nava de pe Terra care aducea cu ea n noi colonisti. Din pacate, in timpul aplanetizarii, unii membri ai grupului sufera un accident si nu mai pot fi salvati. Cum cei ramasi sunt insuficienti numeric pentru a coloniza intreaga planeta, se poate recurge la metoda clonarii (acceptata in acel moment) dar nu a tuturor si nici in acelasi numar de exemplare. Dupa clonare, colonistii se raspandesc pe cele m insule sau continente ale planetei. Pentru a evita degenerarea, grupurile formate, cate unul pentru fiecare insula sau continent, nu trebuie sa contina persoane identice. Pe fiecare insula/continent pot supravietui exact numarul de persoane dat.
Evident, colonistii si-au pus si problema supravietuirii informatiei genetice in caz de catastrofe. intr-o astfel de situatie e necesar sa supravietuiasca cat mai multe exemplare umane distincte. Se pune deci problema determinarii unui numar cat mai mare de grupuri dintre cele raspandite pe planeta, astfel incat oricum s-ar lua doua grupuri din cele selectate, membrii unuia sa se regaseasca ca si clone in celalalt grup.
Date de intrare in fisierul
CLONE.INP:
n - n - numar de colonisti, identificati mai jos prin numar de ordine (1 * n * 200)
m - m - numar de insule/continente (1 * m * 200)
k - k - numar decedati la aplanetizare (0 * k * n)
l
1 l
2 ... l
m - numarul de colonisti din cele m grupuri (li * 200, *i * {1, ..., m})
d
1 d
2 ... d
k- cei k oameni decedati la aplanetizare
c
1 nc
1 - colonistul c
1 se cloneaza in nc1 exemplare
c
2 nc
2 c2 nc
2
... ... ...
c
p nc
p cp nc
p
Date de iesire in fisierul
CLONE.OUT:
e
11 e
12 ... e
1l1 - grupul 1 format dupa clonare
e
21 e
22 ... e
2l2 - grupul 2 format dupa clonare
...
e
m1 e
m2 ... emlm - grupul m format dupa clonare
MAX - numarul de grupuri selectate
e
11 e
12 ... e
1p1 - primul grup selectat
e
21 e
22 ... e
2p2 - al 2-lea grup selectat
...
e
MAX,1 e
MAX,2 ... e
MAX,pMAX - al MAX-lea grup selectat
sau
NU EXISTA SOLUTIE
Observatii:
1. In cazul in care colonistul cj se cloneaza in ncj exemplare, se vor considera ncj+1 clone care se raspandesc pe planeta
2. Colonistii "neclonati" raman intr-un "exemplar"
3. Grupurile selectate se vor afisa in ordinea crescatoare a numarului de membri.
4. Un grup poate fi format dintr-o singura persoana (urmand ca in viitor, in alta problema : -), sa realizeze o alianta )
5. Daca nu exista decedati, fisierul de intrare va avea linia corespunzatoare vida.
Exemplu
pentru datele de intrare:
9
4
4
3 4 1 2
3 4 7 8
2 3
6 2
o posibila iesire corecta este:
2 5 6
1 2 6 9
2
2 6
3
2
2 6
2 5 6
Punctaj: 50 puncte.
Timp de lucru pentru un test: 5 secunde