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

placa.out

3
2

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>