Editing 1515 - Gradina

== Enunț ==
Păcală a reușit să ducă la bun sfârșit înțelegerea cu boierul căruia-i fusese slugă și, conform învoielii, boierul trebuie să-l răsplătească dându-i o parte din livada sa cu pomi fructiferi. Boierul este un om foarte ordonat, așa că livada sa este un pătrat cu latura de N metri unde, pe vremuri, fuseseră plantate N rânduri cu câte N pomi fiecare. Orice pom fructifer putea fi identificat cunoscând numărul rândului pe care se află și poziția sa în cadrul rândului respectiv. Cu timpul, unii pomi s-au uscat şi acum mai sunt doar P pomi. Păcală trebuie să-și delimiteze în livadă o grădină pătrată cu latura de K metri.

== Cerința ==
Cunoscând dimensiunile livezii și grădinii, numărul pomilor din livadă și poziția fiecăruia, determinați numărul maxim de pomi dintr-o grădină pătrată de latură K și numărul modurilor în care poate fi amplasată grădina cu numărul maxim de pomi.

== Date de intrare ==
Fișierul gradinain.txt conține: <br>

* pe prima linie numerele naturale N, P și K, separate prin câte un spațiu, cu semnificaţia din enunţ; <br>
* pe următoarele P linii câte 2 numere naturale Lin și Col, separate printr-un spațiu, reprezentând numărul rândului, respectiv poziția în rând a fiecărui pom din livadă.

== Date de ieșire ==
Fișierul gradinaout.txt va conține:<br>

* pe prima linie numărul maxim de pomi fructiferi dintr-o grădină pătrată cu latura de K metri;<br>
* pe a doua linie numărul de posibilități de a amplasa grădina astfel încât să conțină numărul maxim de pomi determinat.

== Restricții și precizări ==
* 2 &les; '''N''' &les; 1.000
* 1 &les; '''P''' &les; N*N
* 1 &les; '''K''' &les; N

== Exemplul 1 ==
; Intrare
; gradinain.txt
: 12 10 5 
: 4 3 
: 5 5 
: 6 8 
: 7 3 
: 7 7 
: 8 8 
: 9 3 
: 9 6 
: 10 10 
: 11 5
; Ieșire
: Datele de intrare corespund restricțiilor impuse
; gradinaout.txt
: 5
: 5

=== Explicație ===
Grădina lui Păcală poate avea maximum 5 pomi fructiferi. Ea poate fi amplasată în 5 moduri, având colțul stânga-sus de coordonate: (5, 3), (5, 4), (5, 5), (6, 6), (7, 3).

== Exemplul 2 ==
; Intrare
; gradinain.txt
: 1 10 5 
: 4 3 
: 5 5 
: 6 8 
: 7 3 
: 7 7 
: 8 8 
: 9 3 
: 9 6 
: 10 10 
: 11 5
; Ieșire
: Datele de intrare NU corespund restricțiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line>
#1515 - Gradina

def validare_date(n, p, k, pomii):
    if not (2 <= n <= 1000) or not (1 <= p <= n*n) or not (1 <= k <= n):
        return False

    for lin, col in pomii:
        if not (1 <= lin <= n) or not (1 <= col <= n):
            return False

    return True


def numar_maxim_pomi(n, p, k, pomii):
    matrice_pomi = [[0] * n for _ in range(n)]

    for i in range(p):
        lin, col = pomii[i]
        matrice_pomi[lin - 1][col - 1] = 1

    max_pomi = 0
    numar_posibilitati = 0

    for i in range(n - k + 1):
        for j in range(n - k + 1):
            suma_pomi = sum(sum(matrice_pomi[i + x][j + y] for y in range(k)) for x in range(k))
            if suma_pomi > max_pomi:
                max_pomi = suma_pomi
                numar_posibilitati = 1
            elif suma_pomi == max_pomi:
                numar_posibilitati += 1

    return max_pomi, numar_posibilitati


def citire_date_input():
    with open("gradinain.txt", "r") as f:
        n, p, k = map(int, f.readline().split())
        pomii = [tuple(map(int, f.readline().split())) for _ in range(p)]
    return n, p, k, pomii


def scriere_date_output(max_pomi, numar_posibilitati):
    with open("gradinaout.txt", "w") as f:
        f.write(str(max_pomi) + "\n")
        f.write(str(numar_posibilitati) + "\n")


if __name__ == "__main__":
    n, p, k, pomii = citire_date_input()

    if validare_date(n, p, k, pomii):
        print("Datele de intrare corespund restricțiilor impuse")
        max_pomi, numar_posibilitati = numar_maxim_pomi(n, p, k, pomii)
        scriere_date_output(max_pomi, numar_posibilitati)
    else:
        print("Datele de intrare NU corespund restricțiilor impuse")

</syntaxhighlight>