Cod sursa(job #604129)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 20 iulie 2011 16:23:27
Problema Fractal Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
/*
	impart la fiecare pas in sferturi din ce in ce mai mici
si numar sferturile intregi + puntile de legatura.
l1 = 3
l2 = 15
l3 = 63
....
ln = 4 * l(n-1) + 3

fiecare sfert poate avea punctul de start diferit
*/

#include <cstdio>

const int SUS=0,JOS=1,STANGA=2,DREAPTA=3;
const int NV=0,NE=1,SV=2,SE=3;

int n,i,j;
int pasi = 0;
int dist_sfert[4];

int lungime_patrat(int ordin)
{
	if (ordin == 0)
		return 0;
	return 4 * lungime_patrat(ordin - 1) + 3;
}

void preprocesare()
{
	dist_sfert[NV] = 0;
	dist_sfert[SV] = 1;
	dist_sfert[SE] = 2;
	dist_sfert[NE] = 3;
}

void divide_et_impera(int n, int i, int j)
{
	if (n == 0)
		return;
	int sfert=0, i_sfert=i, j_sfert=j;
	
	//aducere i_sfert, j_sfert in cadranul sfertului
	if (i > 1<<(n-1))
	{
		sfert+=2;
		i_sfert -= 1<<(n-1);
	}
	if (j > 1<<(n-1))
	{
		++sfert;
		j_sfert -= 1<<(n-1);
	}
	
	//rotire i_sfert, j_sfert in functie de orientarea sfertului
	//(SV, SE au aceeasi orientare)
	
	
	if (sfert == NV)//transpusa
	{
		int aux = i_sfert;
		i_sfert = j_sfert;
		j_sfert = aux;
	}
	
	if (sfert == NE)//transpusa, i simetric, j simetric
	{
		int aux = i_sfert;
		i_sfert = j_sfert;
		j_sfert = aux;
		
		i_sfert = 1<<(n-1) - i_sfert + 1;
		j_sfert = 1<<(n-1) - j_sfert + 1;
	}
	
	
	pasi += (lungime_patrat(n-1) + 1) * dist_sfert[sfert];
	
	
	divide_et_impera(n-1,i_sfert,j_sfert);
}

int main()
{
	freopen("fractal.in","r",stdin);
	freopen("fractal.out","w",stdout);
	scanf("%d%d%d",&n,&j,&i);
	preprocesare();
	divide_et_impera(n,i,j);
	printf("%d",pasi);
	return 0;
}