2412 - Sub Mat 1 - Revision history

Oros Ioana Diana at 15:05, 18 May 2024

2024-05-18T15:05:24Z

Oros Ioana Diana at 17:13, 8 January 2024

2024-01-08T17:13:56Z

← Older revision		Revision as of 17:13, 8 January 2024
Line 1:		Line 1:
			Se consideră o matrice A cu următoarele proprietăţi:
			*conţine n linii şi m coloane;
			*conţine doar valorile 0 şi 1;
			*pe fiecare linie valorile sunt plasate în ordine crescătoare.
			Definim o submatrice determinată de perechea de linii L1 şi L2 (L1 ≤ L2) şi de perechea de coloane C1 şi C2 (C1 ≤ C2) ca fiind totalitatea elementelor matricei A[i,j] pentru care L1 ≤ i ≤ L2 şi C1 ≤ j ≤ C2.
			Dacă toate elementele unei submatrice sunt egale cu 0, atunci submatricea se numeşte nulă.
			Asupra matricei A putem efectua una sau mai multe operaţii de interschimbări de linii. Prin astfel de interschimbări liniile matricei pot fi rearanjate astfel încât matricea A să conţină cel puţin o submatrice nulă cu număr maxim de elemente.
	== Cerința ==		== Cerința ==
	Fiind dată o astfel de matrice se cere să se determine numărul maxim de zerouri dintr-o submatrice nulă ce se poate obţine printr-o rearanjare a liniilor matricei date.		Fiind dată o astfel de matrice se cere să se determine numărul maxim de zerouri dintr-o submatrice nulă ce se poate obţine printr-o rearanjare a liniilor matricei date.
Line 6:		Line 13:
	Fișierul de ieșire submat1.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul maxim de elemente pe care îl conţine o submatrice nulă rezultată în urma rearanjărilor liniilor matricei A.		Fișierul de ieșire submat1.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul maxim de elemente pe care îl conţine o submatrice nulă rezultată în urma rearanjărilor liniilor matricei A.
	== Restricții și precizări ==		== Restricții și precizări ==
	~ 2 ≤ n, m ≤ 1000		*2 ≤ n, m ≤ 1000
	<br>		<br>
	~ Pentru 60% din teste n, m ≤ 100.		*Pentru 60% din teste n, m ≤ 100.
	== ~~Exemplu~~ 1 ==		== Exemplul 1 ==
	; ~~Intrare~~		; submat1in.txt
	~~: submat1~~.in
	:3 5		:3 5
	:0 0 0 1 1		:0 0 0 1 1
	:0 1 1 1 1		:0 1 1 1 1
	:0 0 0 0 1		:0 0 0 0 1
	; ~~Ieșire~~		; submat1out.txt
	~~: submat1~~.~~out~~
	:6		:6
	<br>		<br>
	== ~~Exemplu~~ 2 ==		== Exemplul 2 ==
	; ~~Intrare~~		; submat1in.txt
	~~: submat1~~.in
	:4 2		:4 2
	:0 0		:0 0
Line 28:		Line 32:
	:0 1		:0 1
	:0 0		:0 0
	; ~~Ieșire~~		; submat1out.txt
	:5		:5
	<br>		<br>
Line 53:		Line 57:

	return rezultat		return rezultat
			def verificare_restrictii(numar): # funcția de verificare a datelor de intrare
			if 2 <= n # adăugăm restricția pentru n
			m <= 1000
			return True
			else:
			return False

	def main():		def main():
	with open("~~submat1~~.in", "r") as file_in:		with open("submat1in.txt", "r") as file_in:
	n, m = map(int, file_in.readline().split())		n, m = map(int, file_in.readline().split())
	matrice = [list(map(int, file_in.readline().split())) for _ in range(n)]		matrice = [list(map(int, file_in.readline().split())) for _ in range(n)]
Line 61:		Line 71:
	rezultat = numar_maxim_zerouri(matrice)		rezultat = numar_maxim_zerouri(matrice)

	with open("~~submat1~~.~~out~~", "w") as file_out:		with open("submat1out.txt", "w") as file_out:
	file_out.write(str(rezultat))		file_out.write(str(rezultat))

Oros Ioana Diana: Pagină nouă: == Cerința == Fiind dată o astfel de matrice se cere să se determine numărul maxim de zerouri dintr-o submatrice nulă ce se poate obţine printr-o rearanjare a liniilor matricei date. == Date de intrare == Fișierul de intrare submat1.in conţine pe prima linie două numere naturale n m, separate printr-un spaţiu, reprezentând numărul de linii, respectiv numărul de coloane ale matricei A. Pe următoarele n linii ale fişierului sunt descrise cele n linii ale matricei...

2023-12-12T18:28:15Z

Pagină nouă: == Cerința == Fiind dată o astfel de matrice se cere să se determine numărul maxim de zerouri dintr-o submatrice nulă ce se poate obţine printr-o rearanjare a liniilor matricei date. == Date de intrare == Fișierul de intrare submat1.in conţine pe prima linie două numere naturale n m, separate printr-un spaţiu, reprezentând numărul de linii, respectiv numărul de coloane ale matricei A. Pe următoarele n linii ale fişierului sunt descrise cele n linii ale matricei...

New page

== Cerința ==
Fiind dată o astfel de matrice se cere să se determine numărul maxim de zerouri dintr-o submatrice nulă ce se poate obţine printr-o rearanjare a liniilor matricei date.
== Date de intrare ==
Fișierul de intrare submat1.in conţine pe prima linie două numere naturale n m, separate printr-un spaţiu, reprezentând numărul de linii, respectiv numărul de coloane ale matricei A. Pe următoarele n linii ale fişierului sunt descrise cele n linii ale matricei A; pe fiecare linie din cele n vor fi scrise câte m valori din mulţimea {0, 1}, separate prin spaţii, reprezentând în ordine elementele liniei respective.
== Date de ieșire ==
Fișierul de ieșire submat1.out va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul maxim de elemente pe care îl conţine o submatrice nulă rezultată în urma rearanjărilor liniilor matricei A.
== Restricții și precizări ==
~ 2 ≤ n, m ≤ 1000
<br>
~ Pentru 60% din teste n, m ≤ 100.
== Exemplu 1 ==
; Intrare
: submat1.in
:3 5
:0 0 0 1 1
:0 1 1 1 1
:0 0 0 0 1
; Ieșire
: submat1.out
:6
<br>
== Exemplu 2 ==
; Intrare
: submat1.in
:4 2
:0 0
:1 1
:0 1
:0 0
; Ieșire
:5
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#2412 - Sub Mat 1
def numar_maxim_zerouri(matrice):
numar_linii = len(matrice)
numar_coloane = len(matrice[0])

matrice.sort(key=lambda linie: linie.count(0), reverse=True)

prefixe = [linie.copy() for linie in matrice]
for i in range(numar_linii):
for j in range(1, numar_coloane):
prefixe[i][j] += prefixe[i][j - 1]

rezultat = 0

for i in range(numar_linii):
for j in range(i, numar_linii):
numar_zerouri = prefixe[j][-1] if i == 0 else prefixe[j][-1] - prefixe[i - 1][-1]
rezultat = max(rezultat, numar_zerouri * (j - i + 1))

return rezultat

def main():
with open("submat1.in", "r") as file_in:
n, m = map(int, file_in.readline().split())
matrice = [list(map(int, file_in.readline().split())) for _ in range(n)]

rezultat = numar_maxim_zerouri(matrice)

with open("submat1.out", "w") as file_out:
file_out.write(str(rezultat))

if __name__ == "__main__":
main()
</syntaxhighlight>