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 2n ș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_imp.in conține pe prima linie numărul n, iar pe celelalte 2n linii câte 2n numere naturale nenule separate prin spații .

Date de ieșire

Fișierul de ieșire matrice_div_et_imp.out va conține o linie cu cele 2n*2n 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

Exemplu 1 :

matrice_div_et_imp.in

1
1 2 
3 4

matrice_div_et_imp.out

1 4 2 3 

Exemplu 2 :

matrice_div_et_imp.in

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

matrice_div_et_imp.out

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

Exemplu 3 :

matrice_div_et_imp.in

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_imp.out

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 

Observație pentru ultimul exemplu : toate numerele sunt pe o singură linie

#include <bits/stdc++.h>

using namespace std;

ifstream cin("matrice_div_et_imp.in");
ofstream cout("matrice_div_et_imp.out");

int m[2001][2001];

void afisare(int sus , int jos , int st , int dr)
{
    if(jos - sus >= 1)
    {
        int mij1=(sus + jos) / 2;
        int mij2=(st + dr) / 2;
        afisare(sus , mij1 , st , mij2);
        afisare(mij1+1 , jos , mij2+1 , dr);
        afisare(sus , mij1 , mij2+1 , dr);
        afisare(mij1+1 , jos , st , mij2);
    }
    else
        cout << m[sus][st] << ' ';
}

int main()
{
    int n;
    cin >> n;
    n = pow(2 , n);
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            cin >> m[i][j];
    afisare(1 , n , 1 , n);
    return 0;
}