Vizualizare sursă pentru „1498 - Ciocolata”

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