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

<syntaxhighlight lang="python" line>

1. 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>