Editing 1206 - Placa

== 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>