1966 - match

Enunt

Tanărul Pagnad proaspăt ajuns la facultate, vrea să prindă și el ceva. Fiind nemulțumit de celebra aplicație Tinder acesta dorește să-și creeze propria lui aplicație. Aplicația se folosește de datele strânse de pe diferite rețele de socializare ale utilizatorului și le codează într-o matrice. Stați calmi, nu trebuie sa creați voi matricea, dar pentru a-și studia compatibilitatea cu o persoana Pagnad se folosește de următoarele noțiuni.

Acesta definește o structură de dimensiune k o submatrice pătratică de latura k. Compatibilitatea se stabilește în funcție de câte perechi de două structuri, nu neapărat de aceleași dimensiuni, dar de sumă egală se găsesc în două matrici (prima structură trebuie să aparțină primei matrici, a doua celei de-a doua matrici).

Definim o structură prin coordonatele colțului stânga sus (x,y) și dimensiunea laturii acesteia k. Două perechi x1, y1, k1 și x2, y2, k2 sunt diferite daca: x1≠x2 sau k1≠k2 sau daca x1=x2 si k1=k2 si y1≠y2 sau x1=x2, y1=y2 si k1≠k2 (acestea fac referință pentru submatrice din aceeași matrice).

Cerinta

Se cere să se afle compatibilitatea între cele două matrice.

Date de intrare

Fișierul de intrare match.in conține pe prima linie numerele n1 si m1. Pe a doua linie se vor găsi n1 numere. Pe următoarea linie n2 și m2, iar pe linia a patra cele n2 numere.

Unde m1 și m2 reprezintă numărul de coloane, iar n1 și n2 reprezintă dimensiunea totala a matricei.

Date de ieșire

Fișierul de ieșire match.out va conține pe prima linie un singur număr, respectiv compatibilitatea dintre cele două matrice.

Restricții și precizări

n1,n2 ≤ 31.000
numerele din matrice <10^9
se garantează că suma acestora este <101^8
m1≤n1; m2≤n2;
(n1,m1)≠1; (n1,m2)≠1, unde (a,b)=cmmdc(a,b);

Exemplul 1

matchin.txt

9 3

1 2 3 4 5 6 7 8 9

9 3

1 2 3 4 5 6 7 8 9

matchout.txt

Datele introduse corespund restrictiilor impuse.

14

Exemplul 2

matchin.txt

10 20

11 12 13 14 15 16 17 18 19

matchout.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

def calculeaza_suma_submatrice(matrice, x, y, k):

   suma = 0
   for i in range(x, x + k):
       for j in range(y, y + k):
           suma += matrice[i][j]
   return suma

def sunt_compatibile(matrice1, matrice2):

   n1, m1 = len(matrice1), len(matrice1[0])
   n2, m2 = len(matrice2), len(matrice2[0])

   for k1 in range(1, n1 + 1):
       for k2 in range(1, n2 + 1):
           for x1 in range(n1 - k1 + 1):
               for y1 in range(m1 - k1 + 1):
                   suma1 = calculeaza_suma_submatrice(matrice1, x1, y1, k1)
                   for x2 in range(n2 - k2 + 1):
                       for y2 in range(m2 - k2 + 1):
                           suma2 = calculeaza_suma_submatrice(matrice2, x2, y2, k2)
                           if suma1 == suma2:
                               print(f"Compatibile: ({x1}, {y1}, {k1}) și ({x2}, {y2}, {k2})"

</syntaxhighlight>