Cod sursa(job #603736)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 18 iulie 2011 14:40:43
Problema Fractal Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 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 sfert_dest[4][4];//[directie_patrat][sfert_destinatie]
int dir_sfert[4][4];//[directie_patrat][sfert_interogat]

void preprocesare_sferturi_pana_la_sfert_destinatie()
{
	sfert_dest[SUS][NV] = 2;
	sfert_dest[SUS][NE] = 1;
	sfert_dest[SUS][SV] = 3;
	sfert_dest[SUS][SE] = 0;
	
	sfert_dest[JOS][NV] = 0;
	sfert_dest[JOS][NE] = 3;
	sfert_dest[JOS][SV] = 1;
	sfert_dest[JOS][SE] = 2;
	
	sfert_dest[STANGA][NV] = 2;
	sfert_dest[STANGA][NE] = 3;
	sfert_dest[STANGA][SV] = 1;
	sfert_dest[STANGA][SE] = 0;
	
	sfert_dest[DREAPTA][NV] = 0;
	sfert_dest[DREAPTA][NE] = 1;
	sfert_dest[DREAPTA][SV] = 3;
	sfert_dest[DREAPTA][SE] = 2;
}

void preprocesare_directie_sferturi()
{
	dir_sfert[SUS][NV] = SUS;
	dir_sfert[SUS][NE] = SUS;
	dir_sfert[SUS][SV] = DREAPTA;
	dir_sfert[SUS][SE] = STANGA;
	
	dir_sfert[JOS][NV] = DREAPTA;
	dir_sfert[JOS][NE] = STANGA;
	dir_sfert[JOS][SV] = JOS;
	dir_sfert[JOS][SE] = JOS;
	
	dir_sfert[STANGA][NV] = STANGA;
	dir_sfert[STANGA][NE] = JOS;
	dir_sfert[STANGA][SV] = STANGA;
	dir_sfert[STANGA][SE] = SUS;
	
	dir_sfert[DREAPTA][NV] = JOS;
	dir_sfert[DREAPTA][NE] = STANGA;
	dir_sfert[DREAPTA][SV] = SUS;
	dir_sfert[DREAPTA][SE] = STANGA;
}

void preprocesare_baza_date_bucati()
{
	preprocesare_sferturi_pana_la_sfert_destinatie();
	preprocesare_directie_sferturi();
}

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

void divide_et_impera(int n, int i, int j, int dir)
{
	if (n == 0)
		return;
	int sfert=0, i_sfert=i, j_sfert=j;
	if (i > 1<<(n-1))
	{
		sfert+=2;
		i_sfert -= 1<<(n-1);
	}
	if (j > 1<<(n-1))
	{
		++sfert;
		j_sfert -= 1<<(n-1);
	}
	pasi += (lungime_patrat(n-1) + 1) * sfert_dest[dir][sfert];
	divide_et_impera(n-1,i_sfert,j_sfert,dir_sfert[dir][sfert]);
}

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