1266 - Cauta Nr In Matrice: Difference between revisions
(9 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
== Cerinta == | == Cerinta == | ||
Se dă o matrice cu n linii şi m coloane ce conţine numere naturale astfel încât parcurgând matricea pe prima linie de la stânga la dreapta, pe a doua linie de la dreapta la stânga, pe a treia linie de la stânga la drepta, ş.a.m.d., toate elementele matricei vor forma un şir strict crescător. Fiind date p numere naturale ordonate strict crescător, să se afişeze pentru fiecare numărul liniei şi coloanei unde acesta se găseşte în matrice, respectiv 0 dacă acesta nu se găseşte în matrice. | Se dă o matrice cu '''n''' linii şi '''m''' coloane ce conţine numere naturale astfel încât parcurgând matricea pe prima linie de la stânga la dreapta, pe a doua linie de la dreapta la stânga, pe a treia linie de la stânga la drepta, ş.a.m.d., toate elementele matricei vor forma un şir strict crescător. Fiind date '''p''' numere naturale ordonate strict crescător, să se afişeze pentru fiecare numărul liniei şi coloanei unde acesta se găseşte în matrice, respectiv '''0''' dacă acesta nu se găseşte în matrice. | ||
== Date de intrare == | == Date de intrare == | ||
Fișierul de intrare | Fișierul de intrare '''cautanrinmatricein.txt''' conține pe prima linie numerele '''n''' şi '''m''' reprezentând dimensiunile matricei , pe următoarele n linii câte m numere aranjate conform enunţului reprezentând elementele matricei, pe următoarea linie numărul p, iar pe ultima linie cele '''p''' numere în ordine strict crescătoare ce trebuie căutate în matrice. | ||
== Date de iesire == | == Date de iesire == | ||
Fișierul de ieșire | Fișierul de ieșire '''cautanrinmatriceout.txt''' va conține pe primele '''p''' linii numărul liniei şi coloanei pe care se află în matrice fiecare din cele '''p''' numere date, respectiv '''0''' dacă numărul nu se găseşte în matrice. | ||
== Restrictii si precizari == | == Restrictii si precizari == | ||
*1 | *'''1 ⩽ n , m ⩽ 1000''' | ||
*elementele matricei sunt numere naturale mai mici decât 2.000.000.000 | *elementele matricei sunt numere naturale mai mici decât '''2.000.000.000''' | ||
*1 | *'''1 ⩽ p ⩽ 1.000.000''' | ||
*cele p numere vor fi mai mici decât 2.000.000.000 | *cele p numere vor fi mai mici decât '''2.000.000.000''' | ||
== Exemplul 1 == | == Exemplul 1 == | ||
; | |||
;cautanrinmatricein.txt | |||
: 3 4 | |||
: 2 5 11 14 | |||
: 29 27 23 19 | |||
: 32 38 44 59 | |||
: 3 | |||
: 11 24 38 | |||
;1 3 | :Datele introduse corespund restrictiilor impuse. | ||
;cautanrinmatriceout.txt | |||
: 1 3 | |||
: 0 | |||
: 3 2 | |||
== Exemplul 2 == | == Exemplul 2 == | ||
;cautanrinmatricein.txt | |||
: 3 2 | |||
: 5 8 | |||
: 12 19 | |||
: 23 21 | |||
:Datele introduse nu corespund restrictiilor impuse. | |||
== Rezolvare == | == Rezolvare == | ||
<syntaxhighlight lang="python3" line="1"> | <syntaxhighlight lang="python3" line="1"> | ||
def | def verifica_restrictiile(n, m, p, matrice, numere_cautate): | ||
if not (1 <= n <= 1000 and 1 <= m <= 1000 and 1 <= p <= 1000000): | |||
return False | |||
matrice = [ | for rand in matrice: | ||
if len(rand) != m: | |||
return False | |||
if len(numere_cautate) != p: | |||
return False | |||
if any(not (1 <= num < 2000000000) for rand in matrice for num in rand) or any(not (1 <= num < 2000000000) for num in numere_cautate): | |||
return False | |||
return True | |||
def cautare_numere_in_matrice(n, m, matrice, p, numere_cautate): | |||
rezultat = [] | |||
for numar in numere_cautate: | |||
gasit = False | |||
for i in range(n): | |||
if i % 2 == 0: | |||
for j in range(m): | |||
if matrice[i][j] == numar: | |||
rezultat.append((i + 1, j + 1)) | |||
gasit = True | |||
break | |||
else: | |||
for j in range(m - 1, -1, -1): | |||
if matrice[i][j] == numar: | |||
rezultat.append((i + 1, j + 1)) | |||
gasit = True | |||
break | |||
if not gasit: | |||
rezultat.append(0) | |||
return rezultat | |||
if __name__ == "__main__": | if __name__ == "__main__": | ||
with open("cautanrinmatricein.txt", "r") as fisier: | |||
n, m = map(int, fisier.readline().split()) | |||
matrice = [list(map(int, fisier.readline().split())) for _ in range(n)] | |||
p = int(fisier.readline()) | |||
numere_cautate = list(map(int, fisier.readline().split())) | |||
if verifica_restrictiile(n, m, p, matrice, numere_cautate): | |||
rezultat = cautare_numere_in_matrice(n, m, matrice, p, numere_cautate) | |||
with open("cautanrinmatriceout.txt", "w") as fisier_out: | |||
for item in rezultat: | |||
if isinstance(item, tuple): | |||
fisier_out.write(f"{item[0]} {item[1]}\n") | |||
else: | |||
fisier_out.write(f"{item}\n") | |||
else: | |||
print("Datele de intrare nu respectă restricțiile specificate.") | |||
</syntaxhighlight> | </syntaxhighlight> | ||
Latest revision as of 15:27, 2 January 2024
Cerinta[edit | edit source]
Se dă o matrice cu n linii şi m coloane ce conţine numere naturale astfel încât parcurgând matricea pe prima linie de la stânga la dreapta, pe a doua linie de la dreapta la stânga, pe a treia linie de la stânga la drepta, ş.a.m.d., toate elementele matricei vor forma un şir strict crescător. Fiind date p numere naturale ordonate strict crescător, să se afişeze pentru fiecare numărul liniei şi coloanei unde acesta se găseşte în matrice, respectiv 0 dacă acesta nu se găseşte în matrice.
Date de intrare[edit | edit source]
Fișierul de intrare cautanrinmatricein.txt conține pe prima linie numerele n şi m reprezentând dimensiunile matricei , pe următoarele n linii câte m numere aranjate conform enunţului reprezentând elementele matricei, pe următoarea linie numărul p, iar pe ultima linie cele p numere în ordine strict crescătoare ce trebuie căutate în matrice.
Date de iesire[edit | edit source]
Fișierul de ieșire cautanrinmatriceout.txt va conține pe primele p linii numărul liniei şi coloanei pe care se află în matrice fiecare din cele p numere date, respectiv 0 dacă numărul nu se găseşte în matrice.
Restrictii si precizari[edit | edit source]
- 1 ⩽ n , m ⩽ 1000
- elementele matricei sunt numere naturale mai mici decât 2.000.000.000
- 1 ⩽ p ⩽ 1.000.000
- cele p numere vor fi mai mici decât 2.000.000.000
Exemplul 1[edit | edit source]
- cautanrinmatricein.txt
- 3 4
- 2 5 11 14
- 29 27 23 19
- 32 38 44 59
- 3
- 11 24 38
- Datele introduse corespund restrictiilor impuse.
- cautanrinmatriceout.txt
- 1 3
- 0
- 3 2
Exemplul 2[edit | edit source]
- cautanrinmatricein.txt
- 3 2
- 5 8
- 12 19
- 23 21
- Datele introduse nu corespund restrictiilor impuse.
Rezolvare[edit | edit source]
<syntaxhighlight lang="python3" line="1">
def verifica_restrictiile(n, m, p, matrice, numere_cautate):
if not (1 <= n <= 1000 and 1 <= m <= 1000 and 1 <= p <= 1000000): return False
for rand in matrice: if len(rand) != m: return False
if len(numere_cautate) != p: return False
if any(not (1 <= num < 2000000000) for rand in matrice for num in rand) or any(not (1 <= num < 2000000000) for num in numere_cautate): return False
return True
def cautare_numere_in_matrice(n, m, matrice, p, numere_cautate):
rezultat = []
for numar in numere_cautate: gasit = False for i in range(n): if i % 2 == 0: for j in range(m): if matrice[i][j] == numar: rezultat.append((i + 1, j + 1)) gasit = True break else: for j in range(m - 1, -1, -1): if matrice[i][j] == numar: rezultat.append((i + 1, j + 1)) gasit = True break
if not gasit: rezultat.append(0)
return rezultat
if __name__ == "__main__":
with open("cautanrinmatricein.txt", "r") as fisier: n, m = map(int, fisier.readline().split()) matrice = [list(map(int, fisier.readline().split())) for _ in range(n)] p = int(fisier.readline()) numere_cautate = list(map(int, fisier.readline().split()))
if verifica_restrictiile(n, m, p, matrice, numere_cautate): rezultat = cautare_numere_in_matrice(n, m, matrice, p, numere_cautate)
with open("cautanrinmatriceout.txt", "w") as fisier_out: for item in rezultat: if isinstance(item, tuple): fisier_out.write(f"{item[0]} {item[1]}\n") else: fisier_out.write(f"{item}\n") else: print("Datele de intrare nu respectă restricțiile specificate.")
</syntaxhighlight>
Explicatie[edit | edit source]
Numărul 11 se află în matrice pe linia 1 coloana 3, numărul 24 nu se află în matrice, iar numărul 38 se află în matrice pe linia 3, coloana 2.