!problema/pandora?poza1.png!
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.
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.
h2. 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
h2. Date de intrare
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
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.
h2. Date de ieșire
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.
Î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$].
h2. Restricții
* 2 ≤ **N** ≤ 1000
* 2 ≤ **M** ≤ 200000
* 3 ≤ **k** < 400
* 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.
* 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
* 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
h2. Exemplu
table(example).
|_. 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 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ă.
!problema/pandora?poza2.png!
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ă.
!problema/pandora?poza2.png!
|
== include(page="template/taskfooter" task_id="pandora") ==
