Vasiliu Costel Andrei: Pagină nouă: == 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 pri...

2023-12-17T19:33:54Z

Pagină nouă: == 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 pri...

New page

== 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 &les; '''N * M''' &les; 400.000
* 1 &les; '''K''' &les; N
* 1 &les; '''L''' &les; M
* 1 &les; '''A[i][j]''' &les; N * M, 1 &les; '''i''' &les; N, 1 &les; '''J''' &les; 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>
#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>

2451 - Mexitate - Revision history