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).

Cerința

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

Date de intrare

Fișierul de intrare matchIN.txt 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 matchOUT.txt 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

• n1,n2 ≤ 31.000
• numerele din matrice <109
• se garantează că suma acestora este <1018
• 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

14

Explicație

Matricile sunt identice, deci se consideră toate submatricele primei matrice.

Exemplul 2:

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 nu corespund restrictiilor impuse

Rezolvare

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()