Cod sursa(job #928591)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 26 martie 2013 15:47:15
Problema Fractal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <fstream>

using namespace std;

//Lungimile unui cadran de marime 2^k
unsigned int lungimi[]={0,3,15,63,255,1023,4095,16383,65535,262143,1048575,4194303,16777215,67108863,268435455,1073741823};

//Puterile lui 2
unsigned int puteri_2[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
int lin,col;

//Functia recursiva ce calculeaza raspunsul
int cat(int k)
{
    //Cazul de baza
    if(k==0)
       return 0;
    else
    {
             int aux;
             k--;
             
             //Primele doua cazuri sunt o simpla micsorare a problemei initiale prin paradigma Divide-et-impera
             if(lin>puteri_2[k])
             {
                 if(col>puteri_2[k])
                 {
                     //cout<<"cadran 3"<<endl;                
                     col-=puteri_2[k];
                     lin-=puteri_2[k];
                     return ((2*lungimi[k])+cat(k)+2);
                  }
                  else
                  {
                      //cout<<"cadran 2"<<endl;
                      lin-=puteri_2[k]; 
                      return ((lungimi[k])+cat(k)+1);    
                  }
              }
             else
             {
                 //Aceste doua cazuri sunt speciale: nu numai ca cele 2 cadrane trebuie rotite, dar si simetrizate pe coloane (dupa rotire)
                 //Dupa aceste operatii,  problema se rezolva folosind recurente asemanatoare cu cele de la cadranele 2 si 3.
                  if(col>puteri_2[k])
                  {
                      //cout<<"cadran 4"<<endl;
                      col-=puteri_2[k];
                      aux=col;
                      col=lin;
                      lin=puteri_2[k]-aux+1;
                      col=puteri_2[k]-col+1;
                      
                      return ((3*lungimi[k])+cat(k)+3);           
                  }
                  else
                  {
                    //cout<<"cadran 1"<<endl;
                     aux=lin; 
                     lin=col;
                     col=puteri_2[k]-aux+1;
                     col=puteri_2[k]-col+1;
                     
                     return (cat(k)); 
                  }
              }
       }
}

int main()
{
    ifstream fin("fractal.in");
    ofstream fout("fractal.out");
    
    int k;
    fin>>k;
    fin>>col>>lin;
    
    fout<<cat(k);
    
    fin.close();
    fout.close();
    return 0;
}