1973 - Hambar2

Enunț

Prințesa Gîrcella este foarte frumoasă. Fiindcă a venit momentul să se mărite, foarte mulți feciori au venit să îi ceară mâna. Printre aceștia se află și Cavalerul de Aur, marele algoritmician. Gîrcella îl dorește pe cel mai inteligent, așa că le va pune o provocare. Grădina sa este o matrice pătratică binară (cu valori 0 sau 1), valorile 0 reprezintă teren liber iar valorile 1 reprezintă pomi. Cel ce va găsi suprafața dreptunghică de arie maximă ce conține doar valori 0, pe care va construi un hambar, va câștiga mâna frumoasei Gîrcella.

Cerința

Ajutați-l pe Cavalerul de Aur să câștige această întrecere.

Date de intrare

Fișierul de intrare hambar2.in conține pe prima linie numerele N și M, reprezentând dimensinunea matricei respectiv numărul de pomi, iar pe următoarele M linii se vor găsi două numere x și y, separate printr-un spațiu, reprezentând indicele liniei, respectiv al coloanei pe care se află un pom.

Date de ieșire

Fișierul de ieșire hambar2.out va conține pe prima linie numărul S, reprezentând aria maximă a unei suprafețe dreptunghiulare. În consolă se va afișa un mesaj de validare a datelor ("Input valid" sau instrucțiuni cu privire la n sau m).

Restricții și precizări

• 1 ≤ N, M ≤ 1000
• Nu se vor afla 2 sau mai mulți pomi în același loc.

Exemplu

hambar2.in

5 5

1 3

2 1

2 5

5 1

5 5

hambar2.out

12

Consolă

Input valid

Rezolvare

<syntaxhighlight lang="python"> nMAX = 1000

def clear(stiva):

   while stiva:
       stiva.pop()

def calculate_histogram(n, mat):

   h = [0] * (n + 1)

   for i in range(1, n+1):
       for j in range(1, n+1):
           if not mat[i][j]:
               h[j] += 1
           else:
               h[j] = 0

   return h

def calculate_left_boundary(n, h):

   st = [0] * (n + 1)
   stiva = []

   for j in range(1, n+1):
       while stiva and h[stiva[-1]] >= h[j]:
           stiva.pop()

       if not stiva:
           st[j] = 0
       else:
           st[j] = stiva[-1]

       stiva.append(j)

   return st

def calculate_right_boundary(n, h):

   dr = [0] * (n + 1)
   stiva = []

   for j in range(n, 0, -1):
       while stiva and h[stiva[-1]] >= h[j]:
           stiva.pop()

       if not stiva:
           dr[j] = n+1
       else:
           dr[j] = stiva[-1]

       stiva.append(j)

   return dr

def calculate_max_rect(n, mat):

   arieMAX = 0

   h = calculate_histogram(n, mat)
   st = calculate_left_boundary(n, h)
   dr = calculate_right_boundary(n, h)

   for j in range(1, n+1):
       arieMAX = max(arieMAX, h[j] * (dr[j] - st[j] - 1))

   return arieMAX

def validate_input(n, m):

   if not 1 <= n <= 1000:
       raise ValueError("n trebuie să fie între 1 și 1000")
       return 0
   if not 1 <= m <= 1000:
       raise ValueError("m trebuie să fie între 1 și 1000")
       return 0
   return 1

if __name__ == '__main__':

   with open('hambar2.in', 'r') as fin, open('hambar2.out', 'w') as fout:
       n, m = map(int, fin.readline().split())
       if validate_input(n, m):
           print("Input valid")

       mat = [[False] * (nMAX + 1) for _ in range(nMAX + 1)]
       for _ in range(m):
           x, y = map(int, fin.readline().split())
           mat[x][y] = True

       fout.write(str(calculate_max_rect(n, mat)))

</syntaxhighlight>

Explicație

Acest cod implementează o soluție pentru problema de a găsi cea mai mare suprafață a unui dreptunghi cu toate elementele sale nealbe într-o matrice dată de dimensiunea n x n. Mai precis, codul conține următoarele funcții:

- Funcția "clear" golește conținutul unei stive date ca argument; - Funcția "calculate_histogram" calculează histograma pentru matricea dată și returnează o listă de dimensiune n+1, unde primul element este 0 și următoarele elemente reprezintă înălțimea coloanelor corespunzătoare din matrice; - Funcțiile "calculate_left_boundary" și "calculate_right_boundary" calculează limitele stângi, respectiv drepte ale dreptunghiurilor care conțin fiecare coloană din matricea dată și care au înălțimile date de histograma calculată anterior. Acestea returnează două liste de dimensiune n+1, unde primul și ultimul element sunt 0, iar restul elementelor reprezintă limitele stângi sau drepte corespunzătoare; - Funcția "calculate_max_rect" calculează cea mai mare suprafață a unui dreptunghi cu toate elementele sale nealbe în matricea dată, folosind funcțiile "calculate_histogram", "calculate_left_boundary" și "calculate_right_boundary"; - Funcția "validate_input" verifică dacă valorile n și m sunt în intervalul [1, 1000] și generează o excepție în caz contrar.

În secțiunea "if __name__ == '__main__':" se deschide fișierul "hambar2.in" pentru citire și fișierul "hambar2.out" pentru scriere, se citește dimensiunea matricei și numărul de elemente albe din aceasta și se verifică dacă valorile introduse sunt valide. Dacă sunt, se construiește matricea folosind elementele citite și se apelează funcția "calculate_max_rect" pentru a calcula cea mai mare suprafață a unui dreptunghi cu toate elementele sale nealbe. Rezultatul este scris în fișierul "hambar2.out".