Cod sursa(job #983259)

Utilizator xaphariusMihai Suteu xapharius Data 11 august 2013 13:13:57
Problema Fractal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <cstdio>
#include <stdlib.h>
#include <math.h>
using namespace std;

int k, x, y, size[16];

void init(){
//	compute sizes of all degrees
	size[0] = 0;
	for(int i = 1; i <= 15; ++i)
		size[i] = size[i-1] * 4 + 3; 
}

int computeNrSteps(int _k, int _x, int _y){
	//printf("%d %d %d\n", _k, _x, _y);
//	anchor _k == 1
	if(_k == 1){
		if(_x == 1 && _y == 1)	
			//quadrant I
			return 0;
		else if(_x == 1 && _y == 2)
			//quadrant II
			return 1;
		else if(_x == 2 && _y == 2)
			//quadrant III
			return 2;
		else if(_x == 2 && _y == 1)
			//quadrant IV
			return 3;
		else 
			throw("_k == 1 wrong coordinates");
	};

//	recursion
	int half = 1 << (_k - 1);
	if(_x <= half && _y <= half)
		//quadrant I - no additional steps
		//point needs to be rotated right and y-inverted for k-1 fractal
		return computeNrSteps(_k - 1, _y, _x) + 0;

	else if(_x <= half && _y >= half + 1)
		//quadrant II - one additional k-1 fractal steps + 1 
		//point doesn't have to be rotated, just scaled for k-1 fractal
		return computeNrSteps(_k - 1, _x, _y - half) + size[_k - 1] + 1;

	else if(_x >= half + 1 && _y >= half + 1)
		//quadrant III - two additional k-1 fractal steps + 2
		//both x and y scaled for k-1 fractal
		return computeNrSteps(_k - 1, _x - half, _y - half) + size[_k - 1]*2 +2;

	else if(_x >= half + 1 && _y <= half)
		//quadrant IV - three addtitiona k-1 fractal steps + 3
		//point rotated left and y-inverted for k-1 fractal
		return computeNrSteps(_k -1 , half - _y + 1, (1<<_k) - _x + 1) + size[_k - 1]*3 + 3;
	else 
		throw("recursion error");

}

int main(){
	freopen("fractali.in", "r", stdin);
	freopen("fractali.out", "w", stdout);

	//read
	scanf("%d %d %d", &k, &x, &y);

	//initialize size vector
	init();

	int nrSteps = computeNrSteps(k, x, y);

	printf("%d", nrSteps);
	fclose(stdin);
	fclose(stdout);
	return 0;
}