Cod sursa(job #1320796)

Utilizator HoreaOrosHorea Oros HoreaOros Data 18 ianuarie 2015 15:16:36
Problema Fractal Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.09 kb
//http://www.infoarena.ro/problema/fractal
#include <stdio.h>
#include <stdlib.h>

int dimensiuneCadran(int k)
{
    int dim = 1;
    while(k > 0)
    {
        dim = dim * 4;
        k--;
    }

    return dim;
}

int NumarPasi(int k, int x, int y)
{
    if(k == 1)
    {
        if(x == 1 && y == 1)
            return 0;
        else if(x == 1 && y == 2)
            return 1;
        else if(x == 2 && y == 2)
            return 2;
        else if(x == 2 && y == 1)
            return 3;
    }
    else
    {
        int rez = 0;
        if(x <= (1 << (k - 1)))
        {
            //cadranul 1 sau 2
            if(y <= (1 << (k - 1)))
            {
                    //cadranul 1
                    if (x == y)
                        rez = NumarPasi(k - 1, x, y);
                    else
                        rez = NumarPasi(k - 1, y, x);
            }
            else
            {
                    // cadranul 2
                    rez = dimensiuneCadran(k - 1) + NumarPasi(k - 1, x, y - (1 << (k - 1)));

            }

        }
        else
        {
            // cadranul 3 sau 4;
            if(y > (1 << (k - 1)))
            {
                    //cadranul 3
                    rez = 2 * dimensiuneCadran(k - 1) + NumarPasi(k - 1, x  - (1 << (k - 1)), y - (1 << (k - 1)));
            }
            else
            {
                    // cadranul 4
                    int n = 1 << (k - 1);
                    int aux;
                    //translatare x;
                    x -= n;
                    aux = n - x + 1;
                    x = n - y + 1;
                    y = aux;
                    //rotire dupa diagonala secundara;
                    rez = 3 * dimensiuneCadran(k - 1) + NumarPasi(k - 1, x, y);
            }
        }
        return rez;
    }
}

int main()
{
    FILE *f, *g;
    int k, x, y;

    f = fopen("fractal.in", "r");
    g = fopen("fractal.out", "w");

    while(fscanf(f, "%d %d %d", &k, &x, &y) > 0)
    {
        fprintf(g, "%d\n", NumarPasi(k, x, y));
    }
    return 0;
}