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

<syntaxhighlight lang="python" line>

1. 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>