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 ⩽ n, m ⩽ 100
• 1 ⩽ Q ⩽ 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">

1. Funcție pentru citirea matricei

def citeste_matrice():

   n, m = map(int, input().split())
   matrice = []
   for _ in range(n):
       linie = list(map(int, input().split()))
       matrice.append(linie)
   return matrice

1. Funcție pentru calculul sumei într-un dreptunghi

def suma_dreptunghi(matrice, i1, j1, i2, j2):

   suma = 0
   for i in range(i1, i2 + 1):
       for j in range(j1, j2 + 1):
           suma += matrice[i][j]
   return suma

1. Citirea matricei

matrice = citeste_matrice()

1. Citirea numărului de întrebări

Q = int(input())

1. Răspunsurile la întrebări

raspunsuri = [] for _ in range(Q):

   i1, j1, i2, j2 = map(int, input().split())
   rezultat = suma_dreptunghi(matrice, i1, j1, i2, j2)
   raspunsuri.append(rezultat)

1. Scrierea rezultatelor în fișier

with open("zoo.txt", "w") as fout:

   for raspuns in raspunsuri:
       fout.write(str(raspuns) + "\n")

</syntaxhighlight>

Explicatie

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