Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | album.in, album.out | Sursă | Concurs Mihai Patrascu 2013 |
| Autor | Paul-Dan Baltescu | Adăugată de |  Ionescu Vlad •vladii |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Album
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.
Date de intrare
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.
Date de ieşire
Î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.
Restricţii
- 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.
Exemplu
| album.in | album.out |
|---|---|
| 3 2 1 2 3 4 5 2 | 2 |
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 prima in rand, astfel devenind vizibili si elevii ei si indeplinindu-se toate conditiile.
