Fişierul intrare/ieşire:pandora.in, pandora.outSursăLot I Juniori 2016
AutorEugen NodeaAdăugată deTiberiu028A Tiberiu Musat Tiberiu02
Timp execuţie pe test0.3 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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 (k*k)-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.inpandora.outExplicatie
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 sa te autentifici pentru a trimite solutii. Click aici