1266 - Cauta Nr In Matrice

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.

Date 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

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

• 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

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

cautanrinmatricein.txt

3 2

5 8

12 19

23 21

Datele introduse nu corespund restrictiilor impuse.

Rezolvare

def cautare_in_matrice(matrice, p, numere_cautate):
    rezultate = []

    for numar in numere_cautate:
        gasit = False
        i, j = 0, 0

        while i < len(matrice) and j < len(matrice[0]):
            if matrice[i][j] == numar:
                gasit = True
                rezultate.append((i + 1, j + 1))  # Linia și coloana în matrice (indexare de la 1)
                break
            elif matrice[i][j] < numar:
                i += 1
            else:
                j += 1

        if not gasit:
            rezultate.append((0, 0))

    return rezultate

def main():
    # Citim datele de intrare din fișier
    with open("cautanrinmatricein.txt", "r") as f:
        n, m = map(int, f.readline().split())
        matrice = [list(map(int, f.readline().split())) for _ in range(n)]
        p = int(f.readline())
        numere_cautate = list(map(int, f.readline().split()))

    # Căutăm fiecare număr în matrice
    rezultate = cautare_in_matrice(matrice, p, numere_cautate)

    # Scriem rezultatele în fișierul de ieșire
    with open("cautanrinmatriceout.txt", "w") as f:
        for rezultat in rezultate:
            f.write(f"{rezultat[0]} {rezultat[1]}\n")

if __name__ == "__main__":
    main()

Explicatie

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.