Editing 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 &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<br>
Submatricile cu două linii și trei coloane sunt:<br>
1 2 3 cu mex-ul 4<br>
2 3 1
<br>
2 3 2 cu mex-ul 5<br>
3 1 4
<br>
2 3 1 cu mex-ul 4<br>
1 1 2
<br>
3 1 4 cu mex-ul 5<br>
1 2 6

Produsul tuturor mex-urilor este: 4 * 5 * 4 * 5 = 400<br>
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>