1461 - Meteoriti

Din cauza blestemelor dușmanilor, asupra plantației de ‘noledge a vrăjitorului Arpsod s-a năpustit o ploaie de…meteoriți. Plantația vrăjitorului e foarte bine delimitată: aceasta are forma unei matrice cu N linii și M coloane, iar în fiecare celulă era plantat câte un fir de ‘noledge. Din motive clare de răzbunare, dușmanii nu s-au mulțumit cu o singură ploaie, astfel, pe plantația vrăjitorului au căzut meteoriți în mai multe reprize. La fiecare repriză, pe fiecare celulă a unui dreptunghi bine delimitat, au căzut exact C meteoriți. După ce ploaia s-a oprit, pe fiecare celulă se afla un “bloc” de piatră de înălțime egală cu numărul meteoriților căzuți în acea celulă. Arpsod, foarte furios, a luat următoarea decizie: va construi un laborator exact peste meteoriții căzuți, de unde își va pedepsi dușmanii. El a hotărât că cel mai bun amplasament pentru acest laborator este la înălțime maximă. Totodată, el își dorește ca laboratorul lui să aibă o suprafață cât mai mare.

Cerința

Deoarece Arpsod şi arhitectul său, Ierdnac, sunt prea ocupaţi să pregătească schița viitorului laborator, vă roagă pe voi să determinați aria maximă a unei suprafețe cu celule învecinate, de înălțime maximă precum și numărul de fire de ‘noledge rămase neatinse după căderea meteoriților ( poate au ratat vreunu’ ! ).

Date de intrare

Pe prima linie a fișierului meteoriti.in se află trei numere naturale separate prin spațiu: N și M, reprezentând dimensiunile plantației și R, reprezentând numărul de reprize de meteoriți. Pe următoarele R linii se vor afla cinci valori separate prin spațiu: r1 c1 r2 c2 C, unde r1 c1 reprezintă coordonatele colțului stânga sus ( linie coloană ) iar r2 c2 coordonatele colțului dreapta jos ( linie coloană ) ale dreptiunghiului pe care vor cădea meteoriți iar C reprezintă numărul de meteoriți ce vor cădea pe fiecare celulă din cele delimitate.

Date de ieșire

În fișierul meteoriti.out se va scrie, pe o singură linie, separate prin spațiu, aria maximă a unei suprafețe de înălțime maximă, formată numai din celule vecine respectiv numărul de fire de ‘noledge neafectate de meteoriți. În consolă se va afișa un mesaj de validare a datelor.

Restricții și precizări

• 4 ≤ N, M ≤ 2.000
• 1 ≤ R ≤ 100.000
• 1 ≤ r1 ≤ r2 ≤ N
• 1 ≤ c1 ≤ c2 ≤ M
• 1 ≤ C ≤ 20.000
• Două celule se consideră vecine dacă au cel puțin o latură comună.
• Înălțimea inițială a celulelor se consideră 0.
• Se garantează că pentru 30% din teste 4 ≤ N, M ≤ 300 și 1 ≤ R ≤ 300
• Pentru rezolvarea corectă a primei cerinţe se acordă 80% din punctajul pe testul respectiv iar pentru rezolvarea corectă a celei de-a doua cerinţe se acordă 20% din punctajul pe testul respectiv
• Fișierul de ieșire TREBUIE să conțină exact DOUĂ valori chiar dacă doriți să rezolvați o singură cerință din cele două
• Dacă îi veți da răspunsul corect vrăjitorului, acesta vă va primi și pe voi prin laboratorul său.
• NU este bine să îl supărați pe vrăjitor!

Exemplu

meteoriti.in

5 6 7

2 2 4 3 1

4 4 4 6 2

1 5 4 6 1

2 5 3 6 1

2 3 4 3 1

5 1 5 3 3

4 2 4 2 1

meteoriti.out

3 12

Consolă

Input valid

Explicație

Matricea după meteoriţi: 0 0 0 0 1 1 0 1 2 0 2 2 0 1 2 0 2 2 0 2 2 2 3 3 3 3 3 0 0 0

Înălțimea maximă este 3 iar aria maximă a unei suprafețe de înălțime 3 este tot 3

Rezolvare

<syntaxhighlight lang="python"> nmax = 2*10**3 dl = [-1, 0, 1, 0] dc = [0, 1, 0, -1]

def is_valid(n, m, k):

   if not(4 <= n <= 2000) or not(4 <= m <= 2000):
       return False
   if not(1 <= k <= 100000):
       return False
   for i in range(k):
       r1, c1, r2, c2, x = meteorites[i]
       if not(1 <= r1 <= r2 <= n) or not(1 <= c1 <= c2 <= m):
           return False
       if not(1 <= x <= 20000):
           return False
   return True

def build():

   global a
   for j in range(m):
       for i in range(1, n):
           a[i][j] += a[i-1][j]
   for i in range(n):
       for j in range(1, m):
           a[i][j] += a[i][j-1]

def inside(x, y):

   return (0 <= x < n) and (0 <= y < m)

def fill(i, j, hmax):

   global was_here
   q = [(i, j)]
   was_here[i][j] = True
   area = 1
   while q:
       f1, f2 = q.pop(0)
       for p in range(4):
           iv, jv = f1+dl[p], f2+dc[p]
           if inside(iv, jv) and a[iv][jv] == hmax and not was_here[iv][jv]:
               area += 1
               was_here[iv][jv] = True
               q.append((iv, jv))
   return area

def solve():

   global was_here
   hmax, amax, area0 = 0, 0, 0
   for i in range(n):
       for j in range(m):
           if a[i][j] >= hmax and not was_here[i][j]:
               area = fill(i, j, a[i][j])
               if a[i][j] == hmax:
                   amax = max(amax, area)
               else:
                   amax = area
               hmax = max(hmax, a[i][j])
           if not a[i][j]:
               area0 += 1
   with open('meteoriti.out', 'w') as f:
       f.write(f"{amax} {area0}")

if __name__=="__main__":

   with open('meteoriti.in', 'r') as f:
       n, m, k = map(int, f.readline().split())
       if not is_valid(n,m,k):
           print("Input invalid")
       else:
           print("Input valid")
       a = [[0] * (nmax + 1) for _ in range(nmax + 1)]
       was_here = [[False] * (nmax + 1) for _ in range(nmax + 1)]
       for i in range(k):
           r1, c1, r2, c2, x = map(int, f.readline().split())
           r1, r2 = r1 - 1, r2 - 1
           c1, c2 = c1 - 1, c2 - 1
           # Marks on matrix
           a[r1][c1] += x
           a[r1][c2 + 1] -= x
           a[r2 + 1][c1] -= x
           a[r2 + 1][c2 + 1] += x
   build()
   solve()

</syntaxhighlight>

Explicație cod

Acest cod este o soluție a unui problema de tip algoritmica, numită "Meteoriți", care implică procesarea unei matrici mari și determinarea unor proprietăți ale acesteia. Scopul problemei este de a găsi aria celui mai mare grup de celule în care valorile din matrice sunt egale și, de asemenea, de a găsi numărul de celule din matrice care au valoarea 0. Intrarea constă în dimensiunile matricei, numărul de meteorite care lovesc matricea și informații despre locul și efectul fiecărui meteorit. Matricea este actualizată în funcție de locurile în care loviturile de meteorit au avut loc. Codul utilizează o abordare de căutare în lățime pentru a determina aria celor mai mari zone în care valorile sunt egale și urmărește și aria zonei cu valoarea maximă. Apoi, rezultatele sunt scrise într-un fișier de ieșire.