Editing 2637 - ZOO

== Cerinta ==

Într-o grădină zoologică reprezentată printr-o matrice '''A''' cu '''n''' linii și '''m''' coloane, fiecare cușcă se află într-o poziție din matrice și conține '''x''' animale. De exemplu, dacă '''A[2][6] = 5''' înseamnă că în cușcă de pe linia 2 și coloana 6 se află '''5 animale'''. Să se răspundă la '''Q''' întrebări de forma '''i1, j1, i2, j2''' unde răspunsul va fi numărul de animale din dreptunghiul din matrice cu cordonatele colțului din stânga sus i1 și j1 și cordonatele colțului din dreapta jos i2 și j2, unde i reprezintă linia și j coloana.

== Date de intrare ==

Fișierul de intrare '''zooin.txt''' conține pe prima linie numerele '''n''' si '''m''', separate printr-un spațiu, iar pe urmatoarele '''n''' linii, câte '''m''' numere, reprezentând matricea. Pe linia '''n + 2''' se află numărul '''Q''', iar pe următoarele '''Q''' linii, câte 4 numere '''(i1 j1 i2 j2)''' cu semnificația din enunț.

== Date de iesire ==

Fișierul de ieșire '''zooout.txt''' pe fiecare linie i răspunsul la întrebarea i.

== Restrictii si precizari ==

*1 &les; n, m &les; 100
*1 &les; Q &les; 100.000
*numărul maxim de animale dintr-o cușcă este de '''1.000.000.000'''
*numerotarea liniilor și a coloanelor din matrice începe de la 1

== Exemplul 1 ==
;zooin.txt
:4 4
:1 2 4 1
:8 1 3 2
:3 1 2 2
:8 1 3 1
:2
:2 2 4 4
:3 1 4 3
;zooout.txt
:Datele introduse corespund restrictiilor impuse
:16
:18

== Exemplul 2 ==
;zooin.txt
:4 3
:-2 5 6
:0 -1 7
:0 0 1
:-8 2 10
:1
:1 1 0 0

:Datele introduse nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def precalculeaza_sume(matrice, n, m):
    sume = [[0] * (m + 1) for _ in range(n + 1)]

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

    return sume

def calculeaza_numar_animale(sume, i1, j1, i2, j2):
    return sume[i2][j2] - sume[i1 - 1][j2] - sume[i2][j1 - 1] + sume[i1 - 1][j1 - 1]

def verifica_rezultate(rezultate_asteptate, rezultate_calculate):
    return all(r1 == r2 for r1, r2 in zip(rezultate_asteptate, rezultate_calculate))

# Citire date de intrare
with open("zooin.txt", "r") as file:
    n, m = map(int, file.readline().split())
    matrice = [list(map(int, file.readline().split())) for _ in range(n)]
    Q = int(file.readline())
    intrebari = [list(map(int, file.readline().split())) for _ in range(Q)]
    rezultate_asteptate = [int(file.readline()) for _ in range(Q)]

# Precalculează sumele parțiale
sume = precalculeaza_sume(matrice, n, m)

# Calcul și afișare rezultate
rezultate_calculate = []
for intrebare in intrebari:
    i1, j1, i2, j2 = intrebare
    rezultate_calculate.append(calculeaza_numar_animale(sume, i1, j1, i2, j2))

# Verificare rezultate
if verifica_rezultate(rezultate_asteptate, rezultate_calculate):
    print("Rezultatele sunt corecte. Scriere în fișierul de ieșire.")
    
    # Scrie rezultatele în fișierul de ieșire
    with open("zooout.txt", "w") as file:
        for rezultat in rezultate_calculate:
            file.write(str(rezultat) + "\n")
else:
    print("Rezultatele nu corespund așteptărilor.")


</syntaxhighlight>

== Explicatie ==

16=1+3+2+1+2+2+1+3+1 si 18=3+1+2+8+1+3