Candale Silviu (silviu) Cerința
Războiul intergalactic a început, iar extratereștrii au invadat deja planeta noastră. Misiunea ta este să salvezi toți locuitorii planetei cât mai repede cu putință!
Într-un hambar vechi, ai găsit un robot proiectat special pentru amplasarea de bombe nucleare și totodată o hartă a planetei sub formă de dreptunghi împărțită în N x M zone pătratice dispuse pe N linii și M coloane, de dimensiune 1. Pe hartă sunt reprezentate și pozițiile extratereștrilor (xi,yi), unde xi reprezintă indicele de linie, iar yi reprezintă indicele de coloană al extraterestrului i. De asemenea, robotul poate amplasa bombe în orice poziție de pe hartă, iar la declanșarea lor, acestea distrug orice extraterestru de pe aceeași linie sau de pe aceeași coloană cu ele.
Din păcate, robotul nu este echipat decât cu o singură bombă. Datoria ta este să-i transmiți robotului coordonatele x y unde să amplaseze bomba, astfel încât toți extratereștrii să fie distruși. Poți să salvezi planeta? Timpul se scurge! Tic, tac, tic, tac…
Date de intrare
Fișierul de intrare bomba.in conține pe prima linie două numere naturale N și M, reprezentând numărul de linii, respectiv numărul de coloane ale hărții. Pe următoarele N linii se găsesc câte M caractere din mulțimea {0,1}; 0 reprezintă o poziție liberă, în timp ce 1 reprezintă o poziție ocupată de un extraterestru.
Date de ieșire
Fișierul de ieșire bomba.out va conține pe prima linie două numere naturale x și y, reprezentând indicele liniei și al coloanei unde trebuie amplasată bomba astfel încât toți extratereștrii să fie distruși.
Restricții și precizări
1 ≤ N, M ≤ 1000- Numărul de extratereștri nu depășește
2000. - Dacă există mai multe celule în care poate fi amplasată bomba, se alege cea cu indicele de linie
xminim. Dacă există mai multe celule în care poate fi amplasată bomba cu indicele de liniexminim, se alege cea cu indicele de coloanăyminim. - Liniile și coloanele hărții sunt numerotate începând cu
1. - Se garantează că pentru datele de test există întotdeauna soluție.
Exemplul 1
bomba.in
4 4 0010 0000 0001 0001
bomba.out
1 4
Explicație
Bomba trebuie să fie amplasată pe poziția (1,4) astfel încât toți extratereștrii să fie distruși.
Exemplul 1
bomba.in
3 3 010 001 000
bomba.out
1 3
Explicație
Bomba poate să fie amplasată atât pe poziția (2,2), cât și pe poziția (1,3), astfel se afișează cea de-a doua poziție deoarece are indicele de linie X minim.