Županijsko natjecanje iz informatike 2019. / Prva podskupina (1. i 2. razred) - 3. zadatak

Mirko je ove godine otišao na skijanje na planinu koju možemo prikazati kao matricu dimenzija N × M.

Broj u svakom polju matrice označava visinu u metrima odgovarajućeg kvadratnog metra planine.

Mirko je odlučio svaki dan spustiti se jednom niz planinu.

Njegov spust opisujemo nizom polja matrice kroz koja se spušta.

Za svako polje Mirkovog spusta (osim početnog) mora vrijediti da je ono strogo manje visine od prethodnog polja spusta, te da s prethodnim poljem dijeli stranicu.

Duljinu spusta definiramo kao broj polja matrice koja spust sadrži.

Trenutačno je zima te je na cijeloj planini snijeg, no dolazi proljeće i snijeg se polako počinje topiti.

Mirko zna da se na manjim nadmorskim visinama snijeg brže topi.

Preciznije, nakon i-tog dana njegovog skijanja više neće biti snijega na dijelovima planine visine i metara.

Mirko želi što bolje iskoristiti ovogodišnje skijanje pa će svakog dana odskijati najdulji mogući spust.

Pomozite Mirku tako da za zadanu planinu ispišete duljinu najduljeg spusta koji Mirko može odskijati za svaki od prvih K dana skijanja, ako znate da Mirko nikad neće pokušavati skijati na dijelovima planine na kojima nema snijega.

ULAZNI PODACI

U prvom retku nalaze se prirodni brojevi N, M i K (1 ≤ N, M ≤ 1000, 1 ≤ K ≤ 1 000 000) iz teksta zadatka.

U svakom od idućih N redaka nalazi se M brojeva ai,j (1 ≤ ai,j ≤ 1 000 000) koji opisuju visine dijelova planine.

IZLAZNI PODACI

Potrebno je ispisati K redaka. U i-ti redak ispišite duljinu najduljeg spusta kojeg Mirko može skijati na iti dan.

Primjeri test podataka

Ulaz

4 4 10
1 3 4 5
7 8 1 9
2 3 4 2
5 1 2 3

Izlaz

5
4
4
3
2
2
2
1
1
0

Objašnjenje

Ulaz

3 5 3
1 2 1 3 2
3 5 4 3 2
3 4 2 1 2

Izlaz

4
4
3