#1206
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:
1
indică prezența în aceea poziție a unei cărămizi, iar un element egal cu 0
indică absența ei;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ă;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
;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
ID | Utilizator | Problema | Data încărcării | Stare | ||
---|---|---|---|---|---|---|
Placa | 10 Octombrie 2022, 20:20 | Evaluare finalizată | 100 |