Rezolvare completă PbInfo #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 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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Matrice_Div_Et_Imp:

#include <iostream>
#include <fstream>


using namespace std ;

ifstream f ("matrice_div_et_imp.in") ;
ofstream g ("matrice_div_et_imp.out") ;

int n , a[520][520] ;

void div_et_imp ( int colt_stanga_i , int colt_stanga_j , int colt_dreapta_i , int colt_dreapta_j )
{
 if ( colt_dreapta_i == colt_stanga_i && colt_dreapta_j == colt_stanga_j )
    g << a[colt_stanga_i][colt_stanga_j] << " " ;
 else if ( colt_stanga_i < colt_dreapta_i && colt_stanga_j < colt_dreapta_j )
        {
         int mi = ( colt_dreapta_i + colt_stanga_i ) / 2 ;
         int mj = ( colt_dreapta_j + colt_stanga_j ) / 2 ;
         div_et_imp ( colt_stanga_i , colt_stanga_j , mi , mj ) ;
         div_et_imp ( mi + 1  , mj + 1 , colt_dreapta_i , colt_dreapta_j ) ;
         div_et_imp ( colt_stanga_i , mj + 1 , mi , colt_dreapta_j ) ;
         div_et_imp ( mi + 1 , colt_stanga_j , colt_dreapta_i , mj ) ;
        }
}


int main ()
{
 int marime ;
 f >> marime ;
 n = 1 ;
 for ( int i = 1 ; i <= marime ; ++i )
    n = n * 2 ;
 for ( int i = 1 ; i <= n ; ++i )
    for ( int j = 1 ; j <= n ; ++j )
        f >> a[i][j] ;
 div_et_imp ( 1 , 1 , n , n ) ;
 return 0 ;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1229 Matrice_Div_Et_Imp

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1229 Matrice_Div_Et_Imp de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!