== include(page="template/taskheader" task_id="album") ==
Poveste şi cerinţă...
Intr-un liceu sunt $N$ clase, iar fiecare clasa are exact $K$ elevi. Cu ocazia promovarii (nu fara emotii) a examenului de Bacalaureat, conducerea liceului a hotarat sa realizeze o serie de poze cu protagonistii acestei minunate generatii. Intr-o poza, clasele se asaza in linie una in spatele alteia cu fata spre aparatul foto. Pentru ca elevii nu au toti aceeasi inaltime, in anumite poze unii dintre ei vor fi ascunsi in spatele altora mai inalti decat ei, stricand astfel poza pentru clasa careia apartin.
Se da o matrice de dimensiuni $N x K$, continand inaltimile elevilor. Se cere numarul minim de poze necesare astfel incat fiecare clasa (dintre cele $N$) sa aiba cel putin o poza in care sa fie vizibili simultan toti elevii ei. In orice poza, elevii oricarei clase se pot permuta intre ei in orice ordine.
h2. Date de intrare
Fişierul de intrare $album.in$ ...
Fişierul de intrare $album.in$ contine pe prima linie $2$ numere naturale $N$ si $K$, despartite printr-un spatiu, semnificand numarul de clase din liceu, respectiv numarul de elevi din fiecare clasa (fiecare clasa are exact acelasi numar $K$ de elevi). Pe urmatoarele $N$ linii se afla cate $K$ numere naturale despartite prin cate un spatiu, reprezentand inaltimile elevilor din clasa respectiva.
h2. Date de ieşire
În fişierul de ieşire $album.out$ ...
În fişierul de ieşire $album.out$ se va afla pe prima linie un singur numar natural, reprezentand numarul minim de poze care trebuie realizate astfel incat fiecare clasa sa aiba cel putin o poza in care toti elevii sai sunt vizibili simultan.
h2. Restricţii
h2. Restricţii si precizari
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1.000$
* $1 ≤ K ≤ 50$
* $1 ≤ inaltimea unui elev ≤ 1.000.000.000$
* Un elev nu este vizibil daca exista in fata sa cel putin un alt elev cu inaltimea mai mare sau egala cu a sa.
* Intr-o clasa, elevii pot fi permutati in orice ordine (nu este obligatoriu sa se aseze exact in ordinea din fisierul de intrare).
* Elevii pot fi permutati doar daca fac parte din aceeasi clasa. Pe un rand se afla o singura clasa (nu pot exista pe un rand elevi din 2 clase diferite).
h2. Exemplu
table(example). |_. album.in |_. album.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 2
1 2
3 4
5 2
| 2
|
h3. Explicaţie
...
O asezare posibila este: in poza 1, in primul rand sta clasa 1, in al doilea rand sta clasa 2, iar in al treilea rand sta clasa 3. Vor fi vizibili simultan toti elevii din clasele 1 si 2. In poza 2, clasa 3 se va aseza in primul rand, astfel devenind vizibili si elevii ei si indeplinindu-se toate conditiile. O imagine edificatoare a acestei asezari este (fotograful se afla in fata primului rand):
3. 2 5 | 2. 4 3
2. 3 4 | 1. 1 2
1. 1 2 | 3. 5 2
In prima poza, clasele se asaza pe randuri in ordinea (1, 2, 3), in a doua poza se asaza in ordinea (3, 1, 2). Se observa ca elevii dintr-o clasa nu pastreaza neaparat ordinea din fisierul de intrare.
== include(page="template/taskfooter" task_id="album") ==
