Cod sursa(job #983288)

Utilizator xaphariusMihai Suteu xapharius Data 11 august 2013 14:01:58
Problema Fractal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 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 = pow(2, _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, pow(2, _k) - _x + 1) + size[_k - 1]*3 + 3;
    else
        throw("recursion error");
 
}
 
int main(){
    freopen("fractal.in", "r", stdin);
    freopen("fractal.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);
}