Vasiliu Costel Andrei: Pagină nouă: == 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 po...

2023-12-27T20:31:30Z

Pagină nouă: == 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 po...

New page

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

1515 - Gradina - Revision history