Catalin Moje at 21:04, 14 May 2023

2023-05-14T21:04:40Z

← Older revision		Revision as of 21:04, 14 May 2023
Line 12:		Line 12:
	==Restricții și precizări==		==Restricții și precizări==

	1 ≤ n ≤ 100		*1 ≤ n ≤ 100
	1 ≤ I ≤ n		*1 ≤ I ≤ n
	coordonatele x y sunt numere întregi, iar puterile p sunt numere naturale		*coordonatele x y sunt numere întregi, iar puterile p sunt numere naturale
	-200 ≤ x , y ≤ 200		*-200 ≤ x , y ≤ 200
	* 1 ≤ p ≤ 30		* 1 ≤ p ≤ 30

	==Exemplu==		==Exemplu==
	===Exemplu1===		===Exemplu1===
			:Intrare:
	bomber.in		;bomber.in
	~~<syntaxhighlight lang="python">~~		;9 5
	9 5		;0 3 2
	0 3 2		;-1 1 3
	-1 1 3		;1 4 1
	1 4 1		;3 4 4
	3 4 4		;-1 -2 3
	-1 -2 3		;3 1 3
	3 1 3		;0 -4 2
	0 -4 2		;3 -2 5
	3 -2 5		;4 -1 2
	4 -1 2
	~~</syntaxhighlight>~~

	~~bomber.out~~
	~~<syntaxhighlight lang="python">~~
	4
	~~</syntaxhighlight>~~

			;bomber.out
			;4

	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python">		<syntaxhighlight lang="python" line="1">

	def validare(n, i, bombe):		def validare(n, i, bombe):

Catalin Moje: Pagină nouă: ==Cerința== Se consideră un poligon militar, pe care este stabilit un sistem de axe de coordonate xOy. Se dau n bombe, numerotate de la 1 la n, pentru fiecare cunoscându-se coordonatele x y și puterea de distrugere p. La explozia unei bombe de putere p se va distruge totul în interiorul și pe cercul de centru x y și rază p, iar dacă există alte bombe în această zonă, vor exploda la rândul lor. Dându-se numărul de ordine I al unei bombe care explodează, să s...

2023-05-04T20:43:39Z

Pagină nouă: ==Cerința== Se consideră un poligon militar, pe care este stabilit un sistem de axe de coordonate xOy. Se dau n bombe, numerotate de la 1 la n, pentru fiecare cunoscându-se coordonatele x y și puterea de distrugere p. La explozia unei bombe de putere p se va distruge totul în interiorul și pe cercul de centru x y și rază p, iar dacă există alte bombe în această zonă, vor exploda la rândul lor. Dându-se numărul de ordine I al unei bombe care explodează, să s...

New page

==Cerința==
Se consideră un poligon militar, pe care este stabilit un sistem de axe de coordonate xOy. Se dau n bombe, numerotate de la 1 la n, pentru fiecare cunoscându-se coordonatele x y și puterea de distrugere p. La explozia unei bombe de putere p se va distruge totul în interiorul și pe cercul de centru x y și rază p, iar dacă există alte bombe în această zonă, vor exploda la rândul lor.

Dându-se numărul de ordine I al unei bombe care explodează, să se determine câte bombe rămân intacte la finalul șirului de explozii declanșate.

==Date de intrare==
ișierul de intrare bomber.in conține pe prima linie numerele n I, fiecare dintre următoarele n linii conține câte trei numere x y p, cu semnificația din enunț.

==Date de ieșire==
Fișierul de ieșire bomber.out va conține pe prima linie numărul C, reprezentând numărul de bombe rămase neexplodate.

==Restricții și precizări==

1 ≤ n ≤ 100
1 ≤ I ≤ n
coordonatele x y sunt numere întregi, iar puterile p sunt numere naturale
-200 ≤ x , y ≤ 200
* 1 ≤ p ≤ 30

==Exemplu==
===Exemplu1===

bomber.in
<syntaxhighlight lang="python">
9 5
0 3 2
-1 1 3
1 4 1
3 4 4
-1 -2 3
3 1 3
0 -4 2
3 -2 5
4 -1 2
</syntaxhighlight>

bomber.out
<syntaxhighlight lang="python">
4
</syntaxhighlight>

==Rezolvare==
<syntaxhighlight lang="python">

def validare(n, i, bombe):
# Verifica daca valorile de intrare sunt valide
if not 1 <= n <= 100:
return False
if not 1 <= i <= n:
return False
for x, y, p in bombe:
if not -200 <= x <= 200 or not -200 <= y <= 200:
return False
if not 1 <= p <= 30:
return False
return True

def rezolvare(n, i, bombe):
# Initializeaza lista de bombe explodate cu bomba i
explodate = [i]
while True:
# Gaseste bombele care trebuie sa explodeze in runda curenta
de_explodat = []
for j, (x, y, p) in enumerate(bombe, start=1):
if j not in explodate and any((x-x0)**2 + (y-y0)**2 <= p0**2 for x0, y0, p0 in (bombe[k-1] for k in explodate)):
de_explodat.append(j)
# Iesirea din bucla while daca nu mai exista bombe de explodat
if not de_explodat:
break
# Adauga bombele care trebuie sa explodeze la lista de bombe explodate
explodate += de_explodat
# Returneaza numarul de bombe neexplodate
return n - len(explodate)

def main():
# Citeste valorile de intrare din fisierul bomber.in
with open('bomber.in') as f:
n, i = map(int, f.readline().split())
bombe = [tuple(map(int, line.split())) for line in f]

# Valideaza datele de intrare
if not validare(n, i, bombe):
print('Date de intrare invalide')
return

# Rezolva problema si afiseaza rezultatul in fisierul bomber.out
with open('bomber.out', 'w') as f:
f.write(str(rezolvare(n, i, bombe)) + '\n')

if __name__ == '__main__':
main()

</syntaxhighlight>

==Explicații ==
În primul rând, codul nostru are nevoie de 3 funcții: validare(), rezolvare() și main(). În funcția validare() se va verifica dacă datele de intrare sunt valide, adică respectă constrângerile problemei. În funcția rezolvare() se va realiza logica necesară pentru a determina numărul de bombe care rămân neexplodate la final. În funcția main() se va apela cele două funcții de mai sus, precum și citirea datelor de intrare și scrierea rezultatului în fișierul de ieșire.

Pasul 1: Validarea datelor de intrare
În funcția validare() se va citi numărul total de bombe, n, și numărul bombei care va exploda prima, i. Dacă datele de intrare nu sunt valide, se va afișa un mesaj corespunzător și se va opri programul. În caz contrar, se va returna True.

Pasul 2: Rezolvarea problemei
În funcția rezolvare() se vor citi coordonatele și puterile de distrugere ale tuturor bombelor, apoi se va construi o listă bombs cu informațiile despre fiecare bombă. Fiecare element din listă va fi o pereche de forma (x, y, p, alive), unde x și y sunt coordonatele bombelor, p este puterea de distrugere a bombei, iar alive este o variabilă booleană care indică dacă bomba este încă în viață sau a fost deja distrusă de o altă bombă.

Apoi se va parcurge lista de bombe și se va verifica dacă fiecare bombă este în raza de acțiune a bombei i care a fost declanșată prima. Dacă da, se va seta variabila alive a respectivei bombe pe False, pentru a indica că aceasta a fost distrusă. Apoi se va parcurge din nou lista de bombe și se va verifica dacă o bombă distrusă poate afecta și alte bombe care se află în raza sa de acțiune. Acest proces se va repeta până când nu mai există nicio bombă care să fi fost distrusă într-o iterație.

La final, se va returna numărul de bombe rămase în viață.

Pasul 3: Citirea datelor de intrare și scrierea rezultatului
În funcția main() se va apela funcția validare() pentru a verifica datele de intrare, apoi se va citi numărul total de bombe, n, și numărul bombei care va exploda prima, i. Apoi se vor citi coordonatele și puterile de distrugere ale tuturor bombelor. După aceea se va apela funcția rezolvare() pentru a determina numărul de bombe rămase în viață, iar rezultatul va fi scris în fișier

0841 - Bomber - Revision history

Catalin Moje at 21:04, 14 May 2023