AndorGiulia: Pagină nouă: Sursă: [https://www.pbinfo.ro/probleme/565/acoperire] == Cerință == Gigel deține un teren de formă dreptunghiulară, împărțite în '''n•m''' sectoare, dispuse pe '''n''' linii și '''m''' coloane. În anumite sectoare sunt instalate camere de luat vederi. Fiecare cameră acoperă anumite sectoare ale terenului, pe diagonală și are o anumită putere '''k''' reprezentând numărul de sectoare pe care le acoperă pe fiecare din cele '''4''' direcții, inclusiv sector...

2023-04-29T11:04:16Z

Pagină nouă: Sursă: [https://www.pbinfo.ro/probleme/565/acoperire] == Cerință == Gigel deține un teren de formă dreptunghiulară, împărțite în '''n•m''' sectoare, dispuse pe '''n''' linii și '''m''' coloane. În anumite sectoare sunt instalate camere de luat vederi. Fiecare cameră acoperă anumite sectoare ale terenului, pe diagonală și are o anumită putere '''k''' reprezentând numărul de sectoare pe care le acoperă pe fiecare din cele '''4''' direcții, inclusiv sector...

New page

Sursă: [https://www.pbinfo.ro/probleme/565/acoperire]
== Cerință ==
Gigel deține un teren de formă dreptunghiulară, împărțite în '''n•m''' sectoare, dispuse pe '''n''' linii și '''m''' coloane. În anumite sectoare sunt instalate camere de luat vederi. Fiecare cameră acoperă anumite sectoare ale terenului, pe diagonală și are o anumită putere '''k''' reprezentând numărul de sectoare pe care le acoperă pe fiecare din cele '''4''' direcții, inclusiv sectorul în care se află camera.
Determinați câte sectoare ale terenului nu sunt acoperite de nici o cameră.
== Date de intrare ==
Programul citește de la tastatură numerele '''n m k''', reprezentând dimensiunile terenului și numărul de camere, apoi '''k''' triplete '''i j p''', reprezentând coordonatele fiecărei camere șî puterea ei.
== Date de ieșire ==
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.". Programul va afișa pe ecran numărul '''C''', reprezentând numărul de sectoare neacoperite. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".
== Restricții și precizări ==
* '''1 ≤ n , m ≤ 1000'''
* '''1 ≤ p ≤ 1000'''
* '''1 ≤ j ≤ m'''
* '''1 ≤ p ≤ min(n,m)'''
* o cameră poate acoperi un sector în care se află o altă cameră
== Exemple ==
=== Exemplu 1 ===
; Date de intrare
: 1 7 2
: 4 2 3
: 4 5 4
; Date de ieșire
: 16
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def citeste_n_m_k():
while True:
try:
n = int(input("Introduceti numarul n: "))
m = int(input("Introduceti numarul m: "))
k = int(input("Introduceti numarul k: "))
if 1 <= n <= 1000 and 1 <= m <= 1000 and 1 <= k <= 1000:
print("Datele sunt corecte.")
return n,m,k
else:
print("Datele nu sunt conform restrictiilor impuse.")
except ValueError:
print("Trebuie introduse doar numere intregi.")

def citeste_triplet(n, m):
valori = []
for i in range(n):
while True:
try:
i,j,p = map(int, input("Introduceti tripletul de valori separate prin spatiu: ").split())
if 1 <= i <= n and 1 <= j <= m and 1 <= p <= min(n,m):
print("Datele sunt corecte.")
valori.append((i,j,p))
break
else:
print("Datele nu sunt conform restrictiilor impuse.")
except ValueError:
print("Trebuie introduse doar valori numerice.")

return valori

def Acoperire(valori, n, m):
a = [[-1 for j in range(m+1)] for i in range(n+1)]
cnt = 0
for i,j,p in valori:
a[i][j] = p
for l in range(1, p+1):
if i + l <= n and j + l <= m:
a[i+l][j+l] = p
if i + l <= n and j - l > 0:
a[i+l][j-l] = p
if i - l > 0 and j + l <= m:
a[i-l][j+l] = p
if i - l > 0 and j - l > 0:
a[i-l][j-l] = p
for i in range(1, n+1):
for j in range(1, m+1):
if a[i][j] == -1:
cnt += 1
return cnt

if _name_ == '_main_':
n, m, k = citeste_n_m_k()
valori = citeste_triplet(k, m)
cnt = Acoperire(valori, n, m)
print("Numarul de sectoare neacoperite este:", cnt)
</syntaxhighlight>
== Explicatie ==
Acest cod este o implementare a unui algoritm care calculează numărul de sectoare neacoperite de o matrice dată, folosind informații despre un set de triplete formate din trei valori întregi (i, j, p) care semnifică: linia i, coloana j și raza de acoperire p a unui sector circular centrare în (i,j).

Funcția citeste_n_m_k() citește de la tastatură valorile pentru n, m și k, reprezentând dimensiunile matricei și numărul de triplete, iar apoi verifică dacă valorile sunt conforme cu restricțiile impuse: n, m și k trebuie să fie între 1 și 1000. Dacă valorile sunt corecte, funcția le returnează.

Funcția citeste_triplet(n, m) primește numărul de triplete k și dimensiunea m și citește de la tastatură k triplete (i, j, p), reprezentând coordonatele centrului sectorului circular și raza de acoperire a acestuia. După citire, funcția verifică dacă tripletele sunt conforme cu restricțiile impuse: i și j trebuie să fie între 1 și n și respectiv între 1 și m, iar p trebuie să fie între 1 și min(n,m). Tripletele valide sunt adăugate la o listă de valori și apoi returnate.

Funcția Acoperire(valori, n, m) primește lista de valori citite anterior și dimensiunile matricei și calculează numărul de sectoare neacoperite. Înainte de a începe procesul de acoperire, se creează o matrice a de dimensiuni n+1 x m+1, inițializată cu valoarea -1 pentru toate elementele, pentru a putea verifica mai ușor dacă un sector a fost acoperit sau nu. Apoi, pentru fiecare triplet de valori citite, se actualizează matricea a, setând valoarea razei p pentru fiecare element de pe cercul centrat în (i,j). Se actualizează de asemenea și elementele din interiorul cercului, mărind raza de la 1 la p. La final, se numără câte elemente din matricea a au valoarea -1, semnificând sectoarele neacoperite, și se returnează acest număr.

Funcția main() apelează funcțiile citeste_n_m_k(), citeste_triplet(k, m) și Acoperire(valori, n, m) și afișează numărul de sectoare neacoperite.

0565 - Acoperire - Revision history