Soluții trimise

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

ID   Utilizator Problema Data încărcării Stare
- - (aZo09IIr89) Placa 27 Martie 2024, 14:19 Evaluare finalizată 0
- - (aZo09IIr89) Placa 27 Martie 2024, 14:19 Evaluare finalizată E.C
- - (aZo09IIr89) Placa 27 Martie 2024, 14:18 Evaluare finalizată E.C
dascalu alexandru (waleks) Placa 27 Martie 2024, 12:57 Evaluare finalizată 100
Tatucu Filip (flipiii) Placa 27 Martie 2024, 12:55 Evaluare finalizată 100
Teodorescu Cosmin-Andrei || Ciurul lui Gheboasa (Cosmin2010) Placa 26 Martie 2024, 17:41 Evaluare finalizată 100
Diaconu Andreea (Andreea0210) Placa 26 Martie 2024, 15:55 Evaluare finalizată 30
Diaconu Andreea (Andreea0210) Placa 26 Martie 2024, 15:54 Evaluare finalizată 100
MINEA GEORGE CHRISTIAN (GEORGE_CHRISTIAN_MINEA) Placa 26 Martie 2024, 15:24 Evaluare finalizată 100
MINEA GEORGE CHRISTIAN (GEORGE_CHRISTIAN_MINEA) Placa 26 Martie 2024, 15:23 Evaluare finalizată 30
Diaconu Andreea (Andreea0210) Placa 26 Martie 2024, 15:21 Evaluare finalizată 0
Biclineru Radu (Radu_Bicli) Placa 24 Februarie 2024, 13:22 Evaluare finalizată 100
Biclineru Radu (Radu_Bicli) Placa 24 Februarie 2024, 12:59 Evaluare finalizată 20
Biclineru Radu (Radu_Bicli) Placa 24 Februarie 2024, 12:58 Evaluare finalizată E.C
Margine Susan (mcristiioan) Placa 29 Ianuarie 2024, 14:37 Evaluare finalizată 100
varlam andra (flower_bee) Placa 26 Ianuarie 2024, 09:00 Evaluare finalizată 0
Măriuță Andra (andramariuta) Placa 16 Ianuarie 2024, 08:16 Evaluare finalizată E.C
Măriuță Andra (andramariuta) Placa 16 Ianuarie 2024, 08:15 Evaluare finalizată E.C
Măriuță Andra (andramariuta) Placa 16 Ianuarie 2024, 08:15 Evaluare finalizată E.C
Anca Leuciuc (AncaLeuciuc) Placa 05 Decembrie 2023, 22:32 Evaluare finalizată 100
Oancea Stefan (PlasNova) Placa 23 Noiembrie 2023, 19:32 Evaluare finalizată E.C
Toma Vlad (VladyInfo) Placa 10 Noiembrie 2023, 17:03 Evaluare finalizată 100
Toma Vlad (VladyInfo) Placa 10 Noiembrie 2023, 16:58 Evaluare finalizată E.C
POPESCU ANDREI (andreip99) Placa 24 Octombrie 2023, 18:30 Evaluare finalizată 100
Puica Stefan (StefanStef99) Placa 24 Octombrie 2023, 12:12 Evaluare finalizată 100
NITA Mioara (Mioara_NITA) Placa 11 Octombrie 2023, 20:16 Evaluare finalizată 100
Bogdan Stefan (stefanbogdan2010) Placa 17 August 2023, 16:15 Evaluare finalizată 100
boeriu horia (horiaboeriu) Placa 14 Iulie 2023, 12:10 Evaluare finalizată 100
Stefan Tiberiu (tiberiustefan) Placa 12 Iulie 2023, 19:51 Evaluare finalizată 100
Bondoc Alexandru (alexbondoc) Placa 18 Mai 2023, 19:33 Evaluare finalizată 100
Draghici Ana (AnaV9382) Placa 13 Mai 2023, 20:17 Evaluare finalizată 100
Draghici Ana (AnaV9382) Placa 13 Mai 2023, 17:49 Evaluare finalizată 31
Stan Alexandru (Ultra980) Placa 13 Mai 2023, 17:00 Evaluare finalizată 21
Boac Mihai Cosmin (Cosminane) Placa 10 Mai 2023, 21:56 Evaluare finalizată 93
Boac Mihai Cosmin (Cosminane) Placa 09 Mai 2023, 23:28 Evaluare finalizată 93
Boac Mihai Cosmin (Cosminane) Placa 09 Mai 2023, 23:27 Evaluare finalizată 83
Boac Mihai Cosmin (Cosminane) Placa 09 Mai 2023, 23:22 Evaluare finalizată 80
Diaconu Tudor (ridiche34) Placa 06 Mai 2023, 17:16 Evaluare finalizată 100
Prof C.N. "Spiru Haret" (flaviusboian) Placa 17 Aprilie 2023, 16:01 Evaluare finalizată 100
Tița Georgiana Teodora (GeorgianaTeodora25) Placa 09 Aprilie 2023, 20:46 Evaluare finalizată 100
c dorina (dorinacodan) Placa 09 Aprilie 2023, 20:45 Evaluare finalizată 100
Maican Iustin (iustincmb) Placa 31 Martie 2023, 19:37 Evaluare finalizată 100
Ion Andrei (AndreiIon2) Placa 31 Martie 2023, 19:35 Evaluare finalizată 100
Ion Andrei (AndreiIon2) Placa 31 Martie 2023, 19:34 Evaluare finalizată 86
Ion Andrei (AndreiIon2) Placa 31 Martie 2023, 19:19 Evaluare finalizată 65
Ion Andrei (AndreiIon2) Placa 31 Martie 2023, 19:16 Evaluare finalizată 48
Ion Andrei (AndreiIon2) Placa 31 Martie 2023, 19:11 Evaluare finalizată 34
Ion Andrei (AndreiIon2) Placa 31 Martie 2023, 19:10 Evaluare finalizată 22
Ion Andrei (AndreiIon2) Placa 31 Martie 2023, 19:09 Evaluare finalizată 7
Ion Andrei (AndreiIon2) Placa 31 Martie 2023, 19:09 Evaluare finalizată E.C