Editing 2554 - Or

== Enunț ==
Se consideră numerele naturale X, N și o matrice pătratică A cu N x N elemente numere naturale.

== Cerința ==
Determinați aria minimă a unei submatrice cu proprietatea că efectuând operația or pe biți or între toate elementele submatricei se obține valoarea X.

== Date de intrare ==
Fișierul de intrare orin.txt conține pe primul rând numerele naturale X și N, separate printr-un spațiu. Pe următoarele N linii sunt câte N elemente numere naturale separate printr-un spațiu, reprezentând elementele matricei.

== Date de ieșire ==
Fișierul de ieșire orout.txt va conține un număr natural reprezentând aria minimă a unei submatrice.

== Restricții și precizări ==
* 2 &les; '''N''' &les; 500
* 1 &les; '''A[i][j]''' &les; 2^31
* Operația pe biți or dintre două numere întregi este un întreg în care al i-lea bit este 0 dacă și numai dacă bitul i din ambele numere este 0.
* Se garantează că pentru toate datele de intrare există mereu o soluție și dimensiunea acesteia este cel puțin 2

== Exemplul 1 ==
; Intrare
; orin.txt
: 11 4
: 5 9 1 8
: 7 7 3 1
: 2 3 1 9
: 5 5 8 7
; Ieșire
: Datele de intrare corespund restricțiilor impuse
; orout.txt
: 3

=== Explicație ===
Submatricea este formată din elementele 3 1 9 de pe linia a treia (3 | 1 | 9 = 11).

== Exemplul 2 ==
; Intrare
; orin.txt
: 11 1
: 5 9 1 8
: 7 7 3 1
: 2 3 1 9
: 5 5 8 7
; Ieșire
: Datele de intrare NU corespund restricțiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line>
#2554 - Or

import functools


def valideaza_input(n, matrice):
    if not 2 <= n <= 500:
        return False

    for rand in matrice:
        for element in rand:
            if not 1 <= element < 2 ** 31:
                return False

    return True


def calculeaza_aria_minima(x, n, matrice):
    aria_minima = float('inf')

    for i in range(n):
        for j in range(n):
            for k in range(i, n):
                for l in range(j, n):
                    submatrice = [rand[j:l + 1] for rand in matrice[i:k + 1]]
                    rezultat_or_pe_biti = functools.reduce(lambda x, y: x | y,
                                                           [element for rand in submatrice for element in rand])

                    if rezultat_or_pe_biti == x:
                        aria_minima = min(aria_minima, (k - i + 1) * (l - j + 1))

    return aria_minima


if __name__ == "__main__":
    with open("orin.txt", "r") as f:
        x, n = map(int, f.readline().split())
        matrice = [list(map(int, f.readline().split())) for _ in range(n)]

    if valideaza_input(n, matrice):
        print("Datele de intrare corespund restricțiilor impuse")

        rezultat = calculeaza_aria_minima(x, n, matrice)

        with open("orout.txt", "w") as f:
            f.write(str(rezultat))
    else:
        print("Datele de intrare NU corespund restricțiilor impuse")
        exit(0)

</syntaxhighlight>