Pagini recente » Cod sursa (job #229217) | Cod sursa (job #319375) | Cod sursa (job #1706397) | Cod sursa (job #1675635) | Cod sursa (job #928591)
Cod sursa(job #928591)
#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;
}