Fișierul intrare/ieșire pandora.in, pandora.out Sursă Lot I Juniori 2016
Autor Eugen Nodea Adăugată de avatar Tiberiu02 Tiberiu Musat Tiberiu02
Timp de execuție pe test 0.3 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Pandora (Lot Juniori)

Anul 2154, undeva pe luxurianta planetă Pandora.
Aici coloniștii RDA (Resources Development Administration) doresc să-și stabilească o bază stelară pentru a exploata rezervele naturale de unobtainium, un minereu rar și prețios aflat din belșug pe munții plutitori (Hallelujah Mountains), munți ce plutesc lent purtați de curenții magnetici asemănător aisbergurilor în mare, pe suprafața planetei formată din gaz lichid.

Pentru prospectarea și exploatarea zăcămintelor de minereu este necesară cartografierea suprafeței planetei șiîn tocmirea unei hărți digitizate reprezentate sub forma unui tablou bidimensional. Astfel, regiunea de interes geologic este împărțită în N×N pătrate teritoriale identice (zone), fiecare zonă fiind identificată prin tripletul (x,y,c) unde (x,y) reprezintă coordonatele zonei teritoriale ( x – linia, y – coloana ), iar c cota (înălțimea). Între zonele ocupate de munții există vaste zone de gaz lichid, zone care au cota 0. Pentru recoltarea și transportul unobtainiumului către baza stelară coloniștii RDA folosesc spice-harvesters, nave speciale cu aterizarea pe verticală. Aterizarea pe munții plutitori reprezintă o adevărată provocare pentru piloții RDA. Pentru a putea ateriza, piloții trebuie să identifice un sector plat (platformă de aterizare), platformă care să respecte designul trenului de aterizare al navelor (vezi figura alăturată). Platforma are forma unui pătrat de latură k ce este format din k*k zone teritoriale, astfel -4 zone au aceeași cotă, iar cele 4 colțuri ale pătratului au cota strict mai mică decât restul zonelor pătratului.

Cerință

Cunoscând descrierea a M zone teritoriale ce alcătuiesc munții plutitori să se determine coordonatele colțului stânga-sus al platformelor de aterizare pentru munții plutitori care permit aterizarea

Date de intrare

Fișierul de intrare pandora.in conține pe prima linie trei numerele naturale N, k și M separate prin câte un spațiu, cu semnificația din enunț. Pe următoarele M linii se află descrierea celor M zone ce alcătuiesc munții plutitori, zone date sub forma unui triplet de numere naturale nenule x, y, c, numerele fiind despărțite prin câte un spațiu.

Date de ieșire

În fișierul de ieșire pandora.out se vor afla scrise, câte o pereche pe linie, coordonatele x, y despărțite prin spațiu, ce reprezintă colțul stânga-sus al platformelor de aterizare pentru fiecare munte plutitor ce permite aterizarea. Dacă nu există platforme de aterizare se va afișa 0.

Restricții

  • 2 ≤ N ≤ 1000
  • 2 ≤ M ≤ 200000
  • 3 ≤ k < 400
  • 1 ≤ x ≤ N, 1 ≤ y ≤ N
  • 0 ≤ c ≤ 1000
  • Prin munte plutitor înțelegem totalitatea zonelor cu cotă nenulă ce sunt împrejmuite de gaz lichid. și sunt vecine pe una din cele 4 direcții: nord, est, sud, vest. Zona muntoasă este compactă, adică nu conține în interior zone cu c=0. Munții sunt despărțiți prin zone de gaz. Harta digitală se consideră mărginită de gaz atmosferic.
  • Platformele de aterizare au cote nenule
  • Dacă un munte are mai multe platforme de aterizare se va determina cea cu coordonată x mai mică, iar la coordonate x egale, cea cu coordonata y mai mică.
  • Pentru 10% dintre teste k < 10. Pentru alte 20% dintre teste N ≤ 500

Exemplu

pandora.in pandora.out Explicatie
9 3 43
1 2 1
1 3 2
1 4 1
2 1 4
2 2 2
2 3 2
2 4 2
3 1 3
3 2 1
3 3 2
3 4 1
1 6 2
1 7 3
1 8 1
2 6 3
2 7 3
2 8 3
2 9 1
3 6 1
3 7 3
3 8 2
5 2 1
5 3 4
5 4 3
6 2 4
6 3 4
6 4 4
6 5 4
7 2 2
7 3 4
7 4 3
7 5 3
8 2 2
8 3 2
6 7 5
6 8 2
6 9 5
7 7 2
7 8 2
7 9 2
8 7 1
8 8 2
8 9 1
1 2
5 2
1 6
Atenție, platforma din dreapta-jos nu este corectă, deoarece
sunt valori din colțuri (valorile de 5) care sunt mai mari
decât valorile din platformă.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii