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:

• pe prima linie numerele naturale N, P și K, separate prin câte un spațiu, cu semnificaţia din enunţ;
  
• 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:

• pe prima linie numărul maxim de pomi fructiferi dintr-o grădină pătrată cu latura de K metri;
  
• 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 ⩽ N ⩽ 1.000
• 1 ⩽ P ⩽ N*N
• 1 ⩽ K ⩽ 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

#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")