2451 - Mexitate

Enunț

Se dă o matrice A cu N linii și M coloane cu elemente numere naturale nu neapărat distincte. Pentru o submatrice definim mex-ul acesteia ca fiind cea mai mică valoare naturală nenulă care nu apare în aceasta.

Cerința

Să se calculeze produsul mex-urilor tuturor submatricelor având K linii și L coloane ale matricei A.

Date de intrare

Fișierul de intrare mexitatein.txt conține pe prima linie patru numere naturale N, M, K şi L separate printr-un spaţiu cu semnificația din enunț. Pe fiecare dintre următoarele N linii se află câte M numere naturale nenule, despărțite prin câte un spațiu, reprezentând valorile matricei.

Date de ieșire

Fișierul de ieșire mexitateout.txt va conține un singur număr natural reprezentând produsul mex-urilor tuturor submatricelor având K linii și L coloane ale matricei modulo 1 000 000 007.

Restricții și precizări

• 1 ⩽ N * M ⩽ 400.000
• 1 ⩽ K ⩽ N
• 1 ⩽ L ⩽ M
• 1 ⩽ A[i][j] ⩽ N * M, 1 ⩽ i ⩽ N, 1 ⩽ J ⩽ M

Exemplul 1

Intrare

mexitatein.txt

3 4 2 3

1 2 3 2

2 3 1 4

1 1 2 6

Ieșire

Datele de intrare corespund restricțiilor impuse

mexitateout.txt

400

Explicație

N = 3, M = 4, K = 2 și L = 3
Submatricile cu două linii și trei coloane sunt:
1 2 3 cu mex-ul 4
2 3 1
2 3 2 cu mex-ul 5
3 1 4
2 3 1 cu mex-ul 4
1 1 2
3 1 4 cu mex-ul 5
1 2 6

Produsul tuturor mex-urilor este: 4 * 5 * 4 * 5 = 400
400 % 1 000 000 007 = 400

Exemplul 2

Intrare

mexitatein.txt

3 4 4 3

1 2 3 2

2 3 1 4

1 1 2 6

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

<syntaxhighlight lang="python" line>

1. 2451 - Mexitate

MOD = 1000000007

def validare_date(n, m, nr_linii, nr_coloane, matrice):

   if not (1 <= n * m <= 400000 and 1 <= nr_linii <= n and 1 <= nr_coloane <= m):
       return False
   for i in range(n):
       for j in range(m):
           if not (1 <= matrice[i][j] <= n * m):
               return False
   return True

def mex(n, m, nr_linii, nr_coloane, matrice):

   result = 1
   for i in range(n - nr_linii + 1):
       for j in range(m - nr_coloane + 1):
           submatrice = [linie[j:j+nr_coloane] for linie in matrice[i:i+nr_linii]]
           valori = set()
           for linie in submatrice:
               valori.update(linie)
           mex = 1
           while mex in valori:
               mex += 1
           result = (result * mex) % MOD
   return result

def main():

   with open("mexitatein.txt", "r") as fin:
       n, m, nr_linii, nr_coloane = map(int, fin.readline().split())
       matrice = [list(map(int, fin.readline().split())) for _ in range(n)]

   if validare_date(n, m, nr_linii, nr_coloane, matrice):
       print("Datele de intrare corespund restricțiilor impuse")
       result = mex(n, m, nr_linii, nr_coloane, matrice)
       with open("mexitateout.txt", "w") as fout:
           fout.write(str(result))
   else:
       print("Datele de intrare NU corespund restricțiilor impuse")
       exit(0)

if __name__ == "__main__":

   main()

</syntaxhighlight>