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 în prag de Stele, 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 K; toate obiectivele aflate la distanţa Manhattan exact K 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 detonează arma în punctul (x, y) cu raza de actiune K, câte din obiective vor fi lovite?
Cred că deja ştiţi cine trebuie să rezolve problema în locul obraznicului Algorel - care nu mai ştie 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 K 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
- Obiectivele se pot suprapune
- Distanta Manahattan intre doua puncte (x1, y1) si (x2, y2) este |x1 - x2| + |y1 - y2|
- Razele sunt numere naturale din intervalul [0, 109]
- Coordonatele obiectivelor şi punctelor de lansare vor fi 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 | 109 | 109 |
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 |
