1266 - Cauta Nr In Matrice: Difference between revisions

From Bitnami MediaWiki
 
(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 cautanrinmatrice.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.
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 cautanrinmatrice.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.
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 n , m 1000
*'''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 p 1.000.000
*'''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 ==
;Intrare
 
;3 4
;cautanrinmatricein.txt
;2 5 11 14
: 3 4
;29 27 23 19
: 2 5 11 14
;32 38 44 59
: 29 27 23 19
;3
: 32 38 44 59
;11 24 38
: 3
;Iesire
: 11 24 38
;Datele introduse corespund restrictiilor impuse.
 
;1 3
:Datele introduse corespund restrictiilor impuse.
;0
;cautanrinmatriceout.txt
;3 2
: 1 3
: 0
: 3 2


== Exemplul 2 ==
== Exemplul 2 ==
;Intrare
;3 2
;5 8
;12 19
;23 21
;Iesire
;Datele introduse nu corespund restrictiilor impuse.


;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 cauta_in_matrice(matrice, numar):
    for i in range(len(matrice)):
        for j in range(len(matrice[i])):
            if matrice[i][j] == numar:
                return i + 1, j + 1  # Adăugăm 1 pentru a afișa linia și coloana în formatul din enunț
    return 0, 0  # Numărul nu a fost găsit în matrice


def main():
def verifica_restrictiile(n, m, p, matrice, numere_cautate):
     # Citirea datelor de intrare din fișier
     if not (1 <= n <= 1000 and 1 <= m <= 1000 and 1 <= p <= 1000000):
     with open("cautanrinmatrice.in", "r") as f:
        return False
         n, m = map(int, f.readline().split())
 
         matrice = [list(map(int, f.readline().split())) for _ in range(n)]
     for rand in matrice:
        p = int(f.readline())
         if len(rand) != m:
         numere_cautate = list(map(int, f.readline().split()))
            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


    # Deschiderea fișierului de ieșire pentru scriere
    with open("cautanrinmatrice.out", "w") as g:
        # Căutarea și scrierea rezultatelor în fișierul de ieșire
        for numar in numere_cautate:
            linie, coloana = cauta_in_matrice(matrice, numar)
            g.write(f"{linie} {coloana}\n")


if __name__ == "__main__":
if __name__ == "__main__":
     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.