Fișierul intrare/ieșire | pandora.in, pandora.out | Sursă | Lot I Juniori 2016 |
---|---|---|---|
Autor | Eugen Nodea | Adăugată de | Tiberiu Musat • Tiberiu02 |
Timp de execuție pe test | 0.3 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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ă. |