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 ⩽ N ⩽ 500
• 1 ⩽ A[i][j] ⩽ 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

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