Fişierul intrare/ieşire:placa.in, placa.outSursăONI 2014 clasa a 7-a
AutorMarius NicoliAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.5 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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

placa.inplaca.outExplicaţii
5 6 3
1 1
2 1
1 2
5 5
1 3
1 1
3
2
Matricea iniţială:
1 1 1 1 1 1
0 1 0 1 0 0
0 0 0 1 1 0
0 0 1 1 1 0
1 1 1 1 1 1
 
Înălţimea minimă este 3 şi se
poate obţine eliminând, de
exemplu, coloanele 3, 4, 5
rezultând matricea:
1 1 1
0 1 0
1 1 1
 
O altă modalitate de a obţine
aceeaşi înălţime dar prin
ştergerea unui număr minim
de coloane (4 şi 5) conduce la:
1 1 1 1
0 1 1 0
1 1 1 1
Trebuie sa te autentifici pentru a trimite solutii. Click aici