0764 - Cirese

Cerinţa

Gigel are o livadă împărțită în n*m sectoare, dispuse pe n linii, numeroate de la 1 la n și m coloane, numerotate de la 1 la m. În fiecare sector se află un cireș, care conține o cantitate de cireșe cunoscută. Gigel va culege toate cireșele din cireșii dispuși într-o zonă dreptunghiulară din livadă. El poate să aleagă între k zone și dorește să culeagă cât mai multe cireșe.

Scrieți un program care determină cantitatea maximă de cireșe pe care o poate culege Gigel din una dintre cele k zone date.

Date de intrare

Programul citește de la tastatură numerele n m k, cu semnificația de mai sus. Apoi citește cantitatea de cireșe din fiecare sector, linie cu linie. Apoi citește k perechi de coordonate i1 j1 i2 j2, unde i1 j1 reprezintă coordonatele (linie coloana) ale colțului stânga-sus al zonei curente, iar i2 j2 reprezintă coordonatele (linie coloana) ale colțului dreapta-jos al zonei curente.

Date de ieșire

Programul va afișa pe ecran numărul C, reprezentând cantitatea maximă de cireșe care poate fi culeasă din una dintre zonele date.

Restricţii şi precizări

• 1 ⩽ n , m , k ⩽ 100
• cantitatea de cireșe din fiecare sector este un număr natural mai mic decât 1000
• 1 ⩽ i1 ⩽ i2 ⩽ n
• 1 ⩽ j1 ⩽ j2 ⩽ m

Exemplu

Intrare

4 6 3

3 1 10 7 5 2

1 5 3 8 6 3

10 1 3 8 10 8

6 1 8 3 9 1

2 2 3 5

1 2 4 6

2 1 4 3

Ieșire

102

Rezolvare

<syntaxhighlight lang="python" line> def validare(n, m, k, ciresi, zone):

   if not isinstance(n, int) or n < 1 or n > 100:
       raise ValueError("Datele de intrare nu corespund restrictiilor impuse")

   if not isinstance(m, int) or m < 1 or m > 100:
       raise ValueError("Datele de intrare nu corespund restrictiilor impuse")

   if not isinstance(k, int) or k < 1 or k > 100:
       raise ValueError("Datele de intrare nu corespund restrictiilor impuse")

   for linie in ciresi:
       for val in linie:
           if not isinstance(val, int) or val < 0 or val > 1000:
               raise ValueError("Datele de intrare nu corespund restrictiilor impuse")

   for z in zone:
       if len(z) != 4 or any(not isinstance(val, int) or val < 1
                             or (val > n and i % 2 == 0) or (val > m and i % 2 == 1) for i, val in enumerate(z)):
           raise ValueError("Datele de intrare nu corespund restrictiilor impuse")

   print("Datele de intrare corespund restrictiilor impuse")
   return True

def main():

   # Solicităm introducerea numerelor n, m și k
   print("Introduceți numerele n, m și k, separate printr-un spațiu: ")
   n, m, k = map(int, input().split())

   # Citim cantitatea de cireșe din fiecare sector
   print("Introduceți cantitatea de cireșe din fiecare sector, linie cu linie: ")
   ciresi = [list(map(int, input().split())) for _ in range(n)]

   # Citim coordonatele zonelor
   print("Introduceți coordonatele zonelor: ")
   zone = [list(map(int, input().split())) for _ in range(k)]

   try:
       validare(n, m, k, ciresi, zone)  # apelul functiei de validare
   except ValueError as e:
       print(e)
       return

   # Inițializăm o matrice de sume parțiale
   suma = [[0] * (m + 1) for _ in range(n + 1)]

   # Calculăm suma parțială pentru fiecare sector
   for i in range(1, n + 1):
       for j in range(1, m + 1):
           suma[i][j] = suma[i - 1][j] + suma[i][j - 1] - suma[i - 1][j - 1] + ciresi[i - 1][j - 1]

   max_ciresi = 0

   for z in zone:
       # Actualizăm cantitatea maximă de cireșe dacă este cazul
       i1, j1, i2, j2 = z
       max_ciresi = max(max_ciresi, suma[i2][j2] - suma[i2][j1 - 1] - suma[i1 - 1][j2] + suma[i1 - 1][j1 - 1])

   # Afișăm cantitatea maximă de cireșe pe care Gigel o poate culege
   print("Cantitatea maximă de cireșe pe care Gigel o poate culege este: ", max_ciresi)

if __name__ == "__main__":

   main()

</syntaxhighlight>

Explicatie

Cantitatea de cireșe care pot fi culese din zona a doua este 102 și este mai mare decât cantitățile din celelalte două zone.