0841 - Bomber

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

Intrare:

bomber.in

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

bomber.out

4

Rezolvare

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

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