1229 - Matrice Div Et Imp

Cerința

Marian a fost foarte interesat de metoda divide et impera și a primit de la profesorul său o problemă: se dă o matrice de dimensiune 2^n și ea trebuie parcursă după o anumită regulă bazată pe divide et impera. Pe baza a trei exemple, el trebuie să descopere regula și s-o aplice . Din păcate, acesta nu reusește și vă cere ajutorul. Vrea o rezolvare foarte eficienta atât din punct de vedere al timpului de execuție cât și a limitei de memorie.

Date de intrare

Fișierul de intrare matrice_div_et_impin.txt conține pe prima linie numărul n, iar pe celelalte 2^n linii câte 2^n numere naturale nenule separate prin spații.

Date de ieșire

Fișierul de ieșire matrice_div_et_impout.txt va conține o linie cu cele 2^n*2^n numere ale matricei , parcurse după respectiva regulă.

Restricții și precizări

• 0 ≤ n ≤ 9
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000

Exemplul 1

matrice_div_et_impin.txt

1

1 2

3 4

matrice_div_et_impout.txt

Datele introduse corespund restricțiilor impuse.

1 4 2 3

Exemplul 2

matrice_div_et_impin.txt

2

15 12 13 14

36 56 34 58

98 80 79 11

10 43 47 50

matrice_div_et_impout.txt

Datele introduse corespund restricțiilor impuse.

15 56 12 36 79 50 11 47 13 58 14 34 98 43 80 10

Exemplul 3

matrice_div_et_impin.txt

3

1 2 3 4 5 6 7 8

9 10 11 12 13 14 15 16

17 18 19 20 21 22 23 24

25 26 27 28 29 30 31 32

33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48

49 50 51 52 53 54 55 56

57 58 59 60 61 62 63 64

matrice_div_et_impout.txt

Datele introduse corespund restricțiilor impuse.

1 10 2 9 19 28 20 27 3 12 4 11 17 26 18 25 37 46 38 45 55 64 56 63 39 48 40 47 53 62 54 61 5 14 6 13 23 32 24 31 7 16 8 15 21 30 22 29 33 42 34 41 51 60 52 59 35 44 36 43 49 58 50 57

Exemplul 4

matrice_div_et_impin.txt

2

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 1000000001

matrice_div_et_impout.txt

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

# 1229 - Matrice Div Et Imp
def validare(dimensiune_n, lista_matrice1):           # functia de validare a datelor de intrare
    if dimensiune_n < 0 or dimensiune_n > 9:
        raise ValueError

    for linie in lista_matrice1:
        for numar in linie:
            if numar < 1 or numar > 1000000000:
                raise ValueError

    fisier_iesire.write("Datele de intrare corespund restrictiilor impuse\n")


def parcurgere(dimensiune_n, lista_matrice1, x, y):  # functia de rezolvare
    if dimensiune_n == 0:
        return [lista_matrice1[x][y]]
    else:
        dimensiune_n -= 1
        dim = 2 ** dimensiune_n
        return (parcurgere(dimensiune_n, lista_matrice1, x, y) +
                parcurgere(dimensiune_n, lista_matrice1, x + dim, y + dim) +
                parcurgere(dimensiune_n, lista_matrice1, x, y + dim) +
                parcurgere(dimensiune_n, lista_matrice1, x + dim, y))


if __name__ == '__main__':
    fisier_intrare = open("matrice_div_et_impin.txt", "r")         # declararea fisierelor
    fisier_iesire = open("matrice_div_et_impout.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)

    try:
        dim_n = int(fisier_intrare.readline())
        lista_matrice = [list(map(int, fisier_intrare.readline().split())) for _ in range(2**dim_n)]

        validare(dim_n, lista_matrice)                 # apelul functiei de validare
        rezultat = parcurgere(dim_n, lista_matrice, 0, 0)  # apelul functiei de rezolvare
        fisier_iesire.write(' '.join(map(str, rezultat)) + '\n')

    except ValueError:
        fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")