AjM: Pagină nouă: == Enunt == 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 un...

2024-06-03T17:30:27Z

Pagină nouă: == Enunt == 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 un...

New page

== Enunt ==
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ţa ==
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 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 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 şi precizări ==
* 1 ≤ N ≤ 100.000; 1 ≤ M ≤ 100.000; 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;
== Exemplu ==
; placa.in
5 6 3
1 1
2 1
1 2
5 5
1 3
1 1
; placa.out
3
2
<br>

== Explicație ==
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
== Rezolvare ==
<syntaxhighlight lang="python" line>
def can_obtain_height(board, k, height):
n, m = len(board), len(board[0])

# Numărăm coloanele consecutive cu 0 de la început și sfârșit
zeros_left = [0] * m
zeros_right = [0] * m

for j in range(m):
for i in range(n):
if board[i][j] == 1:
break
zeros_left[j] += 1

for i in range(n - 1, -1, -1):
if board[i][j] == 1:
break
zeros_right[j] += 1

# Verificăm dacă putem elimina cel mult k coloane pentru a obține înălțimea height
for j in range(1, m):
if zeros_left[j] + zeros_right[j] >= height:
continue
removed = 0
for jj in range(j, min(j + k, m)):
removed += min(zeros_left[jj], height - zeros_right[jj])
if removed > k:
break
if removed <= k:
return True
return False

def min_height(board, k):
low, high = 2, len(board)
while low < high:
mid = (low + high) // 2
if can_obtain_height(board, k, mid):
high = mid
else:
low = mid + 1
return low

def main():
with open("placa.in", "r") as fin:
N, M, K = map(int, fin.readline().split())
board = [list(map(int, fin.readline().split())) for _ in range(M)]

min_h = min_height(board, K)

removed_cols = min(K, max(0, min_h - 2))

with open("placa.out", "w") as fout:
fout.write(f"{min_h}\n")
fout.write(f"{removed_cols}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1206 - Placa - Revision history