1940 - Bomba
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 bombain.txt 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 bombaout.txt 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 ⩽ 1.000
- 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 x minim. Dacă există mai multe celule în care poate fi amplasată bomba cu indicele de linie x minim, se alege cea cu indicele de coloană y minim.
- 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
- Intrare
- bombain.txt
- 4 4
- 0010
- 0000
- 0001
- 0001
- Ieșire
- Datele de intrare corespund restricțiilor impuse
- bombaout.txt
- 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 2
- Intrare
- bombain.txt
- 3 3
- 010
- 001
- 000
- Ieșire
- Datele de intrare corespund restricțiilor impuse
- bombaout.txt
- 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.
Exemplul 3
- Intrare
- bombain.txt
- 3001 3
- 010
- 001
- 000
- Ieșire
- Datele de intrare NU corespund restricțiilor impuse
Rezolvare
<syntaxhighlight lang="python" line>
- 1940 - Bomba
def validare_date(n, m, harta):
if not (1 <= n <= 1000 and 1 <= m <= 1000):
return False
if len(harta) != n:
return False
for linie in harta:
if len(linie) != m:
return False
if not all(caracter in {'0', '1'} for caracter in linie):
return False
return True
def gaseste_pozitie_bomba(n, m, harta):
for coloana in range(m):
for linie in range(n):
if harta[linie][coloana] == '1':
return linie + 1, coloana + 2
with open("bombain.txt", "r") as fin:
n, m = map(int, fin.readline().split()) harta = [fin.readline().strip() for _ in range(n)]
if validare_date(n, m, harta):
print("Datele de intrare corespund restricțiilor impuse")
x, y = gaseste_pozitie_bomba(n, m, harta)
with open("bombaout.txt", "w") as fout:
fout.write(f"{x} {y}\n")
else:
print("Datele de intrare NU corespund restricțiilor impuse")
exit(0)
</syntaxhighlight>