Editing 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 <code>k</code> o submatrice pătratică de latura <code>k</code>. 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 <code>(x,y)</code> și dimensiunea laturii acesteia <code>k</code>. Două perechi <code>x1</code>, <code>y1</code>, <code>k1</code> și <code>x2</code>, <code>y2</code>, <code>k2</code> sunt diferite daca: <code>x1≠x2</code> sau <code>k1≠k2</code> sau daca <code>x1=x2</code> si <code>k1=k2</code> si <code>y1≠y2</code> sau <code>x1=x2</code>, <code>y1=y2</code> si <code>k1≠k2</code> (acestea fac referință pentru submatrice din aceeași matrice).

= Cerința =
Se cere să se afle compatibilitatea între cele două matrice.

= Date de intrare =
Fișierul de intrare <code>matchIN.txt</code> conține pe prima linie numerele <code>n1</code> si <code>m1</code>. Pe a doua linie se vor găsi <code>n1</code> numere. Pe următoarea linie <code>n2</code> și <code>m2</code>, iar pe linia a patra cele <code>n2</code> numere.

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

= Date de ieșire =
Fișierul de ieșire <code>matchOUT.txt</code> va conține pe prima linie un singur număr, respectiv compatibilitatea dintre cele două matrice. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>n1,n2 ≤ 31.000</code>
* numerele din matrice <code><109</code>
* se garantează că suma acestora este <code><1018</code>
* <code>m1≤n1</code>; <code>m2≤n2</code>;
* <code>(n1,m1)≠1</code>; <code>(n1,m2)≠1</code>, unde <code>(a,b)=cmmdc(a,b)</code>;

= Exemplul 1: =
<code>matchIN.txt</code>
 9 3
 1 2 3 4 5 6 7 8 9
 9 3
 1 2 3 4 5 6 7 8 9
<code>matchOUT.txt</code>
 14

=== Explicație ===
Matricile sunt identice, deci se consideră toate submatricele primei matrice.

== Exemplul 2: ==
<code>matchIN.txt</code>
 9 3
 1 2 3 4 5 6 7 8 9
 9 3
 1 2 3 4 5 6 7 8 9
<code>matchOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==

<syntaxhighlight lang="python3" line="1">
def check_restrictions(n1, m1, n2, m2):
    if n1 > 31000 or n2 > 31000 or m1 > n1 or m2 > n2:
        return False
    if (n1, m1) == (1, 1) or (n1, m2) == (1, 1):
        return False
    return True

def load_data(filename):
    global n1, n2, m1, m2, N1, N2, a, b

    with open(filename, 'r') as fin:
        N1, m1 = map(int, fin.readline().split())
        n1 = N1 // m1
        if not check_restrictions(n1, m1, n1, m1):
            return False
        a = [[0 for _ in range(m1)] for _ in range(n1)]
        for i in range(n1):
            a[i] = list(map(int, fin.readline().split()))
        
        N2, m2 = map(int, fin.readline().split())
        n2 = N2 // m2
        if not check_restrictions(n2, m2, n2, m2):
            return False
        b = [[0 for _ in range(m2)] for _ in range(n2)]
        for i in range(n2):
            b[i] = list(map(int, fin.readline().split()))

    return True

MOD = 666013
NMAX = 175

a = [[0 for _ in range(NMAX)] for _ in range(NMAX)]
b = [[0 for _ in range(NMAX)] for _ in range(NMAX)]
pd = [[0 for _ in range(NMAX)] for _ in range(NMAX)]
dp = [[0 for _ in range(NMAX)] for _ in range(NMAX)]
v = {i: [] for i in range(MOD + 1)}

def fasuma():
    global dp, pd, a, b
    # Ajustarea indexării pentru Python, începând de la 0
    for i in range(1, n1 + 1):
        for j in range(1, m1 + 1):
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + a[i-1][j-1]

    for i in range(1, n2 + 1):
        for j in range(1, m2 + 1):
            pd[i][j] = pd[i-1][j] + pd[i][j-1] - pd[i-1][j-1] + b[i-1][j-1]

def pp(s, x):
    return {'s': s, 'x': x}

def bagahash(x):
    r = x % MOD
    for element in v[r]:
        if element['s'] == x:
            element['x'] += 1
            return
    v[r].append(pp(x, 1))

def cauta(x):
    r = x % MOD
    for element in v[r]:
        if element['s'] == x:
            return element['x']
    return 0

def main():
    if not load_data('matchIN.txt'):
        with open('matchOUT.txt', 'w') as fout:
            fout.write("Datele nu corespund restrictiilor impuse\n")
        return
    
    fasuma()

    sol = 0
    # Calcularea și compararea sumelor submatricilor
    for k in range(1, min(n1, m1) + 1):
        for i in range(k, n1 + 1):
            for j in range(k, m1 + 1):
                s = dp[i][j] - dp[i-k][j] - dp[i][j-k] + dp[i-k][j-k]
                bagahash(s)
    for k in range(1, min(n2, m2) + 1):
        for i in range(k, n2 + 1):
            for j in range(k, m2 + 1):
                s = pd[i][j] - pd[i-k][j] - pd[i][j-k] + pd[i-k][j-k]
                sol += cauta(s)
    
    with open('matchOUT.txt', 'w') as fout:
        fout.write(f'{sol}\n')

if __name__ == '__main__':
    main()

</syntaxhighlight>