Fișierul intrare/ieșire	placa.in, placa.out	Sursă	ONI 2014 clasa a 7-a
Autor	Marius Nicoli	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.5 sec	Limită de memorie	32768 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Placa (clasa a 7-a)

Un gard este format din mai multe plăci dreptunghiulare. Fiecare placă este, la rândul ei, construită din NxM cărămizi. Una dintre plăci ridică o problemă, deoarece este deteriorată. Placa este reprezentată pe hârtie cu ajutorul unei matrice cu N linii și M coloane, numerotate de la 1 la N, respectiv de la 1 la M. Matricea conține doar valori 0 și 1, și respectă următoarele reguli:

• un element egal cu 1 indică prezența în aceea poziție a unei cărămizi, iar un element egal cu 0 indică absența ei;
• linia 1 și linia N conțin numai valori egale cu 1, pentru că marginea de sus și cea de jos a plăcii este intactă;
• din orice element egal cu 1, situat în interiorul matricei, se poate ajunge pe linia 1 sau pe linia N sau pe amândouă, mergând doar în sus sau doar în jos, parcurgând numai valorile egale cu 1;
• există cel puțin o coloană stabilă (formată numai din elemente egale cu 1).

Se dorește modificarea plăcii și pentru aceasta se pot șterge din matrice maximum K coloane alăturate. După ștergere se alipesc coloanele rămase și se deplasează pe verticală partea de sus a plăcii spre cea de jos, până când se va forma o coloană stabilă.

Cerință:

Să se determine înălțimea minimă Hmin pe care o poate avea placa ștergând cel mult K coloane alăturate. Identificați numărul minim de coloane alăturate care trebuie șterse pentru a obține înălțimea Hmin.

Date de intrare

Din fișierul de intrare placa.in se citesc de pe prima linie 3 numere naturale N, M, K separate prin câte un spațiu, având semnificația din enunț. Pe fiecare dintre următoarele M linii ale fișierului se găsesc perechi de numere naturale N1, N2, separate printr-un spațiu. Astfel pe linia i+1 a fișierului de intrare numărul N1 reprezintă numărul de elemente de 1 situate pe coloana i, începând cu linia 1, deplasându-ne în „jos” până la întâlnirea unei valori egale cu 0, sau până se ajunge pe linia N; numărul N2 reprezintă numărul de elemente de 1 situate pe coloana i, începând cu linia N, deplasându-ne în „sus” până la întâlnirea unei valori egale cu 0, sau până se ajunge pe linia 1.

Date de ieșire

În fișierul de ieșire placa.out se va scrie pe prima linie înălțimea minimă cerută Hmin, iar pe a doua linie numărul minim de coloane ce trebuie eliminate pentru a obține înălțimea Hmin.

Restricții

• 1 ≤ N ≤ 100000; 1 ≤ M ≤ 100000; 1 ≤ K < M
• se garantează că pe liniile ce conțin informații referitoare la cele M coloane ale matricei există cel puțin o linie pe care se află valoarea N de 2 ori, în rest suma celor două valori este strict mai mică decât N
• toate valorile din fișier sunt strict pozitive
• se acordă 30% din punctajul pe test dacă doar prima valoare e corectă și 70% din punctajul pe test dacă doar a doua valoare e corectă

Exemplu