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 şi M, reprezentând numărul de obiective respectiv numărul de întrebări pentru care Algorel vrea sa afle răspunsul. Urmează N linii ce conţin câte două numere întregi reprezentând coordonatele unui obiectiv. Următoarele M linii descriu câte o întrebare prin trei numere separate prin spaţii: x y r având semnificaţia de mai sus.
Date de ieşire
În fişierul de ieşire grendizer.out veţi afişa pe câte o linie răspunsul pentru fiecare din cele M întrebări.
Restricţii şi precizări
- Obiectivele se pot suprapune
- Distanţa Manahattan între două puncte (x1, y1) şi (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 întregi din intervalul [-MAX_MOD, +MAX_MOD]
- Următorul tabel specifică valorile pentru N, M şi 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 |
