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 ("Input valid" sau "Input invalid" după caz).

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

nmax = 2*10**3
# liste care stochează schimbările de linie și coloană pentru a putea naviga în matricea 2D a meteoritelor din program
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
            a[r1][c1] += x
            a[r1][c2 + 1] -= x
            a[r2 + 1][c1] -= x
            a[r2 + 1][c2 + 1] += x
    build()
    solve()

Explicație cod

Acest program prelucrează date de intrare din fișierul "meteoriti.in", verifică dacă datele de intrare sunt valide și determină cea mai mare zonă de teren afectată de meteorit și numărul total de zone afectate într-un teren reprezentat prin matricea a.

Funcția "is_valid" verifică dacă dimensiunile matricei și numărul de evenimente sunt în intervalul specificat și dacă coordonatele și intensitățile meteoritilor sunt, de asemenea, în intervalul specificat.

Funcția "build" construiește matricea a prin adunarea sumei în direcția verticală și orizontală, astfel încât a[i][j] să conțină suma de la (0,0) la (i,j) în matricea de intrare.

Funcția "inside" verifică dacă coordonatele sunt în interiorul matricei.

Funcția "fill" utilizează o parcurgere BFS (Breadth-First-Search) pentru a găsi cea mai mare zonă continuă de teren cu aceeași înălțime în jurul unui punct dat din matricea a. Aceasta returnează numărul de celule din zona respectivă.

Funcția "solve" utilizează funcția "fill" pentru a căuta zonele de teren cu aceeași înălțime și pentru a determina cea mai mare zonă de teren afectată de meteorit și numărul total de zone afectate. Rezultatele sunt afișate în fișierul "meteoriti.out".

În funcția principală, datele de intrare sunt citite din fișierul "meteoriti.in", verificate și prelucrate prin funcțiile "build" și "solve".