Fişierul intrare/ieşire:grendizer.in, grendizer.outSursăStelele Informaticii 2009, clasele 9-10
AutorSilviu-Ionut GanceanuAdăugată desilviugSilviu-Ionut Ganceanu silviug
Timp execuţie pe test0.65 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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ţă de punctul de detonare 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:
Test12345678910
N850020 00030 00040 00050 00060 00070 00090 000105
M450020 00030 00040 00050 00060 00070 00090 000105
MAX_MOD10100300300300105105105108108

Exemplu

grendizer.ingrendizer.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content