Andrada378: Pagină nouă: == Enunț == După un rezultat slăbuț la un concurs de informatică, Cristina s-a cam supărat. Dan vrea să-i ridice moralul și știe că cel mai bun mod în care poate face asta este ciocolata. Totuși, Dan nu este dispus să-i ofere Cristinei toată ciocolata pe care o are (și el a avut un rezultat slab la concurs, deci.. și el trebuie să-și ridice moralul). Astfel, îi propune Cristinei următoarea ofertă: ”Desenează pe o hârtie un caroiaj format din N linii...

2024-01-03T20:40:39Z

Pagină nouă: == Enunț == După un rezultat slăbuț la un concurs de informatică, Cristina s-a cam supărat. Dan vrea să-i ridice moralul și știe că cel mai bun mod în care poate face asta este ciocolata. Totuși, Dan nu este dispus să-i ofere Cristinei toată ciocolata pe care o are (și el a avut un rezultat slab la concurs, deci.. și el trebuie să-și ridice moralul). Astfel, îi propune Cristinei următoarea ofertă: ”Desenează pe o hârtie un caroiaj format din N linii...

New page

== Enunț ==
După un rezultat slăbuț la un concurs de informatică, Cristina s-a cam supărat. Dan vrea să-i ridice moralul și știe că cel mai bun mod în care poate face asta este ciocolata. Totuși, Dan nu este dispus să-i ofere Cristinei toată ciocolata pe care o are (și el a avut un rezultat slab la concurs, deci.. și el trebuie să-și ridice moralul).

Astfel, îi propune Cristinei următoarea ofertă: ”Desenează pe o hârtie un caroiaj format din N linii și M coloane pe care îl umple cu valori întregi. Cristina va primi un număr de pătrățele de ciocolată egal cu suma valorilor dintr-un dreptunghi ales de ea.”

Deoarece Cristina este prea bosumflată ca să rezolve această “provocare” și prea obosită ca să-l convingă pe Dan să-i dea ciocolata pur și simplu, vă roagă pe voi să o ajutați. (Poate primiți și voi niște ciocolată dacă rezolvați problema. Poate…)

== Cerința ==
Cunoscându-se configurația caroiajului, determinați numărul maxim de pătrățele de ciocolată pe care Cristina îl poate obține alegând un dreptunghi din matrice, precum și coordonatele celor patru colțuri ale acestuia

== Date de intrare ==
Fișierul ciocolatain.txt conține pe prima linie două numere naturale N și M reprezentând numărul de linii și numărul de coloane ale caroiajului. Pe următoarele N linii se găsesc câte M valori întregi reprezentând valorile din caroiaj.

== Date de ieșire ==
Fisierul ciocolataout.txt va conține pe prima linie numărul maxim de pătrățele de ciocolată care se poate obține. Pe a doua linie se vor afla patru numere naturale reprezentând coordonatele colțurilor stânga- sus și dreapta-sus (în această ordine) a dreptunghiului ales. Pe cea de-a treia linie se vor afla tot patru numere naturale reprezentând coordonatele colțurilor stânga-jos și dreapta-jos (în această ordine) a dreptunghiului ales.

== Restricții și precizări ==

* 1 ≤ N, M ≤ 500
* Valorile din caroiaj aparțin intervalului [ -2.000.000.000 , 2.000.000.000 ]
* În cazul în care există mai multe dreptunghiuri din care se obține aceeași valoare maximă, se va alege cel cu indicele de linie al colțului stânga-sus minim. În cazul în care există mai multe dreptunghiuri cu această proprietate, se va alege cel ce are și indicele de coloană al colțului stânga-sus minim. Dacă există mai multe soluții cu proprietatea că au colțul stânga-sus cu indicii de linie și de coloană minimi, se va alege cel cu indicele de linie al coltului dreapta-jos minim. Dacă mai rămân soluții multiple, se va alege cel care are și indicele de coloană al colțului dreapta-jos minim.
* (schematic: valoare maximă → indice linie stânga-sus minim → indice coloană stânga-sus minim → indice linie dreapta-jos minim → indice coloană dreapta-jos minim )
* Se garantează că nici Cristinei și nici lui Dan nu li se va face rău de la ciocolată.

== Exemplu: ==
'''ciocolatain.txt'''

5 9

3 4 -12 4 6 7 -9 5 12

0 4 5 7 9 -5 1 1 5

0 98 34 0 1 7 -7 1 1

6 7 8 -9 0 -2 3 5 22

47 62 -31 55 0 -83 23 77 -10

'''ciocolataout.txt'''

362

1 1 1 9

5 1 5 9

== Explicație ==
Dreptunghiul determinat de punctele (1, 1), (1, 9), (5, 1), (5, 9).

== Rezolvare ==
<syntaxhighlight lang="python">
def is_valid_input(n, m, a):
if not (1 <= n <= 500) or not (1 <= m <= 500):
return False

for i in range(n):
for j in range(m):
if not (-2_000_000_000 <= a[i][j] <= 2_000_000_000):
return False

return True

def citeste_input(file_name="ciocolatain.txt"):
with open(file_name, "r") as file:
n, m = map(int, file.readline().split())
a = [list(map(int, file.readline().split())) for _ in range(n)]

if not is_valid_input(n, m, a):
raise ValueError("Input invalid")

return n, m, a

def scrie_output(smax, x1, y1, lx, ly, file_name="ciocolataout.txt"):
with open(file_name, "w") as file:
file.write(f"{smax}\n")
file.write(f"{x1} {y1} {x1} {y1 + ly}\n")
file.write(f"{x1 + lx} {y1} {x1 + lx} {y1 + ly}\n")

def gaseste_subsir_maxim(n, m, a):
s = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
for j in range(1, m + 1):
s[i][j] = a[i - 1][j - 1] + s[i - 1][j]

smax, x1, y1, lx, ly = 0, 0, 0, 0, 0

for p in range(1, n + 1):
for q in range(p, n + 1):
sum_val = 0
lasty = 1
for j in range(1, m + 1):
s1 = s[q][j] - s[p - 1][j]
sum_val += s1
if sum_val < 0:
sum_val = 0
lasty = j + 1
if sum_val > smax or (sum_val == smax and (p < x1 or (p == x1 and lasty < y1))):
smax = sum_val
x1 = p
y1 = lasty
lx = q - p
ly = j - lasty

return smax, x1, y1, lx, ly

if __name__ == "__main__":
n, m, a = citeste_input()
smax, x1, y1, lx, ly = gaseste_subsir_maxim(n, m, a)
scrie_output(smax, x1, y1, lx, ly)
</syntaxhighlight>

1498 - Ciocolata - Revision history