AndorGiulia at 11:20, 29 April 2023

2023-04-29T11:20:48Z

← Older revision		Revision as of 11:20, 29 April 2023
Line 1:		Line 1:
	Sursă: [pbinfo.ro/probleme/3389/colturi-dr]		Sursă: [https://www.pbinfo.ro/probleme/3389/colturi-dr]
	== Cerință ==		== Cerință ==
	Se dă o matrice cu '''n''' linii și '''m''' coloane cu valori de '''0''' și '''1'''. Numim '''dreptunghi de extrem''' un dreptunghi ale cărui vârfuri au valori egale. Determinați numărul acestor dreptunghiuri, aria dreptunghiului de arie maximă și câte dreptunghiuri au aceeași valoare a vârfurilor ca și dreptunghiul de arie maximă.		Se dă o matrice cu '''n''' linii și '''m''' coloane cu valori de '''0''' și '''1'''. Numim '''dreptunghi de extrem''' un dreptunghi ale cărui vârfuri au valori egale. Determinați numărul acestor dreptunghiuri, aria dreptunghiului de arie maximă și câte dreptunghiuri au aceeași valoare a vârfurilor ca și dreptunghiul de arie maximă.

AndorGiulia: Pagină nouă: Sursă: [pbinfo.ro/probleme/3389/colturi-dr] == Cerință == Se dă o matrice cu '''n''' linii și '''m''' coloane cu valori de '''0''' și '''1'''. Numim '''dreptunghi de extrem''' un dreptunghi ale cărui vârfuri au valori egale. Determinați numărul acestor dreptunghiuri, aria dreptunghiului de arie maximă și câte dreptunghiuri au aceeași valoare a vârfurilor ca și dreptunghiul de arie maximă. == Date de intrare == Fișierul de intrare '''colturi_dr.in''' conține...

2023-04-29T11:20:11Z

Pagină nouă: Sursă: [pbinfo.ro/probleme/3389/colturi-dr] == Cerință == Se dă o matrice cu '''n''' linii și '''m''' coloane cu valori de '''0''' și '''1'''. Numim '''dreptunghi de extrem''' un dreptunghi ale cărui vârfuri au valori egale. Determinați numărul acestor dreptunghiuri, aria dreptunghiului de arie maximă și câte dreptunghiuri au aceeași valoare a vârfurilor ca și dreptunghiul de arie maximă. == Date de intrare == Fișierul de intrare '''colturi_dr.in''' conține...

New page

Sursă: [pbinfo.ro/probleme/3389/colturi-dr]
== Cerință ==
Se dă o matrice cu '''n''' linii și '''m''' coloane cu valori de '''0''' și '''1'''. Numim '''dreptunghi de extrem''' un dreptunghi ale cărui vârfuri au valori egale. Determinați numărul acestor dreptunghiuri, aria dreptunghiului de arie maximă și câte dreptunghiuri au aceeași valoare a vârfurilor ca și dreptunghiul de arie maximă.
== Date de intrare ==
Fișierul de intrare '''colturi_dr.in''' conține pe prima linie numărul '''n''' de linii, numărul '''m''' de coloane, iar pe următoarele linii se află cele '''n * m''' numere naturale.
== Date de ieșire ==
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.". Fișierul de ieșire '''colturi_dr.out''' va conține pe prima linie numerele '''nr, A si cnt''' reprezentând cele trei numere specificate în cerință. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".
== Restricții și precizări ==
* '''1 ≤ n, m ≤ 100'''
* numărul de dreptunghiuri de extrem cu vârfuri de '''1''' este diferit de numărul de dreptunghiuri de extrem cu vârfuri de '''0'''.
* un '''dreptunghi de extrem''' are cel puțin două linii și două coloane
== Exemple ==
=== Exemplu 1 ===
; '''colturi_dr.in'''
: 5 5
: 1 1 1 1 0
: 0 1 1 0 1
: 0 1 0 0 1
: 1 0 1 0 1
; '''colturi_dr.out'''
: 11 25 9
==== Explicatie ====
Sunt '''9''' dreptunghiuri de extrem a cărui vârfuri sunt '''1''', respectiv '''2''' ale cărui vârfuri sunt '''0'''. Dreptunghiul de extrem de arie maximă are colțul stânga sus la '''(0,0)''' și colțul dreapta jos la '''(5,5)'''.
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def citire_matrice():
# Deschide fișierul de intrare și citește n, m și p
with open("colturi_dr.in", "r") as fin:
line = fin.readline().split()
if len(line) != 2:
print("Datele nu sunt conform restrictiilor impuse.")
exit()
n, m = map(int, line)
if not (1 <= n <= 100 and 1 <= m <= 100):
print("Datele nu sunt conform restrictiilor impuse.")
exit()
matrice = []
# Citește matricea din fișierul de intrare
for i in range(n):
row = list(map(int, fin.readline().split()))
# Verifică dacă elementele matricei sunt conform cerințelor
if not all(x in [0, 1] for x in row):
print("Datele nu sunt conform restrictiilor impuse.")
exit()
matrice.append(row)
return n, m, matrice

def colturi_dr(n, m, matrice):
nr = 0 # Numărul dreptunghiurilor de extrem
max_area = 0 # Aria maximă a dreptunghiului de extrem
max_cnt = 0 # Numărul dreptunghiurilor cu aceeași arie maximă
for i in range(n - 1):
for j in range(m - 1):
if matrice[i][j] == matrice[i][j + 1] == matrice[i + 1][j] == matrice[i + 1][j + 1]:
nr += 1
area = (i + 2) * (j + 2)
if area > max_area:
max_area = area
max_cnt = 1
elif area == max_area:
max_cnt += 1
return nr, max_area, max_cnt

if _name_ == "_main_":
n, m, matrice = citire_matrice()
nr, max_area, cnt = colturi_dr(n, m, matrice)
with open("colturi_dr.out", "w") as fout:
fout.write(str(nr) + " " + str(max_area) + " " + str(cnt) + "\n")
print("Numărul de dreptunghiuri de extrem este:", nr)
print("Aria maximă a unui dreptunghi de extrem este:", max_area)
print("Numărul de dreptunghiuri cu aceeași arie maximă este:", cnt)
</syntaxhighlight>
== Explicatie ==
Acest cod implementează o funcție numită citire_matrice() care citește datele de intrare dintr-un fișier colturi_dr.in. Datele de intrare conțin trei valori: n și m, reprezentând dimensiunile unei matrici de dimensiune nxm, și o matrice binară cu n linii și m coloane. Matricea este formată din 0-uri și 1-uri, și reprezintă un tip special de matrice numit "matrice de extrem" (dreptunghiurile de extrem), care conține doar dreptunghiuri cu colțurile de aceeași valoare.

Funcția citire_matrice() validează datele de intrare și returnează o tuplă formată din n, m și matricea citită.

Funcția colturi_dr() primește dimensiunile matricei și matricea în sine și calculează numărul de dreptunghiuri de extrem, aria maximă a unui dreptunghi de extrem și numărul de dreptunghiuri cu aceeași arie maximă.

În final, programul scrie datele de ieșire în fișierul colturi_dr.out și le afișează pe ecran.

3389 - Colturi DR - Revision history

AndorGiulia at 11:20, 29 April 2023