Fişierul intrare/ieşire:album.in, album.outSursăConcurs Mihai Patrascu 2013
AutorPaul-Dan BaltescuAdăugată devladiiIonescu Vlad vladii
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 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).

Exemplu

album.inalbum.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 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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content