Cod sursa(job #2012326)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 18 august 2017 15:27:21
Problema Fractal Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
/*
Impart recursiv fiecare cadran in 4 mai mici de ordin k-1, pana ajung la punct si adun
costurile de deplasare(de exemplu daca punctul e in cadranul 3 adun costurile de
deplasare prin cadranele 1 si 2).
*/
#include<fstream>
using namespace std;
ifstream fi("fractal.in");
ofstream fo("fractal.out");
int k,x,y;

int CostCadaran(int ordin)
{
    int nr=0,i;
    for(i=1; i<=ordin; i++)
    {
        nr=nr*4+3;
    }
    return nr+1;
}

int DetCadran(int x, int y, int ordin)
{
    int n=(1<<ordin);
    if(y<=n/2)
    {
        if(x<=n/2)
            return 1;
        else
            return 2;
    }
    else
    {
        if(x<=n/2)
            return 4;
        else
            return 3;
    }
}

long long Solve(int ordin, int x, int y)
{
    long long cost=0LL;
    int cad=DetCadran(x,y,ordin);
    if(ordin==1)
    {
        return cad-1;
    }
    cost=(cad-1)*CostCadaran(ordin-1);
    int new_x;
    int new_y;
    int n=(1<<ordin);
    //in cazul cadrannului 1 se inverseaza indicii din cauza ca
    //piesa se roteste cu 270 de grade
    switch(cad)
    {
        case 1: new_x=y;
                new_y=x;
                break;
        case 2: new_x=x-n/2;
                new_y=y;
                break;
        case 3: new_x=x-n/2;
                new_y=y-n/2;
                break;
        case 4: new_x=n-y+1;
                new_y=n/2-x+1;
                break;
    }
    return cost+Solve(ordin-1,new_x,new_y);
}

int main()
{
    fi>>k>>x>>y;
    fo<<Solve(k,x,y)<<"\n";
    fi.close();
    fo.close();
    return 0;
}