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

2023-12-29T20:22:17Z

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

New page

== 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>

2554 - Or - Revision history