Detalii evaluare #50110711

Rezumat problemă

#1206 Placa

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ă.

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.

ONI GIM 2014, Clasa a VII-a

Detalii

Problema Placa Operații I/O placa.in/placa.out
Limita timp 0.5 secunde Limita memorie Total: 32 MB / Stivă 32 MB
Id soluție #50110711 Utilizator Tatucu Filip (flipiii)
Fișier placa.cpp Dimensiune 1.23 KB
Data încărcării 27 Martie 2024, 12:55 Scor / rezultat 100 puncte

Evaluare


Mesaj compilare


Rezultat evaluare

Test Timp Mesaj evaluare Scor posibil Scor obținut
0 0 secunde Cerinta a - corect. Cerinta b - corect. 10 10
1 0 secunde Cerinta a - corect. Cerinta b - corect. 10 10
2 0.004 secunde Cerinta a - corect. Cerinta b - corect. 10 10
3 0 secunde Cerinta a - corect. Cerinta b - corect. 10 10
4 0.016 secunde Cerinta a - corect. Cerinta b - corect. 10 10
5 0.016 secunde Cerinta a - corect. Cerinta b - corect. 10 10
6 0.016 secunde Cerinta a - corect. Cerinta b - corect. 10 10
7 0.012 secunde Cerinta a - corect. Cerinta b - corect. 10 10
8 0.02 secunde Cerinta a - corect. Cerinta b - corect. 10 10
9 0.016 secunde Cerinta a - corect. Cerinta b - corect. 10 10
Punctaj total 100

Cum funcționează evaluarea?

www.pbinfo.ro permite evaluarea a două tipuri de probleme:

  • probleme la care rezolvarea presupune scrierea unui program complet
  • probleme la care rezolvarea presupune scrierea unei secvențe de program - câteva instrucțiuni, o listă de declarații, una sau mai multe funcții, etc.

Problema Placa face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:

  • Programul sursă este compilat folosind compilatorul corespunzător. Dacă în urma compilării se obțin erori sau avertismente, acestea sunt afișate în această pagină.
  • Dacă programul a fost compilat, executabilul obținut va fi rulat, furnizându-i-se unul sau mai multe seturi de date de intrare, în concordanță cu restricțiile specifice problemei. Pentru fiecare set de date se obține un anumit punctaj, în raport cu corectitudinea soluției tale.

Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.