Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | grendizer.in, grendizer.out | Sursă | Stelele Informaticii 2009, clasele 9-10 |
| Autor | Silviu-Ionut Ganceanu | Adăugată de |  Silviu-Ionut Ganceanu •silviug |
| Timp execuţie pe test | 0.325 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Grendizer
Grendizer, robotul din serialul de desene animate urmărit de Algorel, are o nouă armă. Această armă funcţionează în felul următor: Grendizer işi stabileşte un punct de detonare şi o rază de acţiune r; toate obiectivele aflate la distanţa Manhattan exact r faţă vor fi lovite.
Algorel a inventariat cele N obiective pe care Grendizer le are de distrus într-unul din episoade. Acum îşi pune întrebări de genul: dacă Grendizer ar detona arma în punctul (x, y) cu o rază de acţiune r, câte din obiective vor fi lovite?
Cred că deja ştiţi cine trebuie să rezolve problema în locul obraznicului Algorel - care nu îşi mai aduce aminte niciun algoritm de când cu desenele animate.
Date de intrare
Fişierul de intrare grendizer.in conţine pe prima linie două numere naturale, N si M, reprezentând numarul de obiectiv respectiv numarul de intrebari pentru care Algorel vrea sa afle raspunsul. Urmeaza N linii ce contin cate doua numere intregi reprezentand coordonatele unui obiectiv. Urmatoarele M linii descriu cate o intrebare prin trei numere separate prin spatii: x y r avand semnificatia de mai sus.
Date de ieşire
În fişierul de ieşire grendizer.out veti afisa M linii cu raspunsul pentru fiecare din cele M intrebari.
Restricţii şi precizări
- Obiectivele se pot suprapune
- Distanta Manahattan intre doua puncte (x1, y1) si (x2, y2) este |x1 - x2| + |y1 - y2|
- Razele de acţiune sunt numere naturale din intervalul [1, 109]
- Coordonatele obiectivelor şi punctelor de lansare vor fi numere intregi din intervalul [-MAX_MOD, +MAX_MOD]
- Urmatorul tabel specifică valorile pentru N, M si MAX_MOD pentru fiecare test:
| Test | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| N | 8 | 500 | 20 000 | 30 000 | 40 000 | 50 000 | 60 000 | 70 000 | 90 000 | 105 |
| M | 4 | 500 | 20 000 | 30 000 | 40 000 | 50 000 | 60 000 | 70 000 | 90 000 | 105 |
| MAX_MOD | 10 | 100 | 300 | 300 | 300 | 105 | 105 | 105 | 108 | 108 |
Exemplu
| grendizer.in | grendizer.out |
|---|---|
| 8 4 2 0 1 -1 0 -2 -1 -1 -2 0 -1 1 0 2 1 1 0 0 2 1 1 2 -1 -1 4 0 0 1000000000 | 8 4 3 0 |
