Cod sursa(job #1903221)

Utilizator tanduraDomnita Dan tandura Data 5 martie 2017 01:13:15
Problema Fractal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <stdio.h>

const unsigned int max_lvl[16] = {0, 3, 15, 63, 255, 1023, 4095, 16383, 65535, 262143, 1048575, 4194303, 16777215, 67108863, 268435455, 1073741823};
const unsigned int max_index[16] = {0, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768};

unsigned int map[5][5] = {
                            {0, 0, 0},
                            {0, 0, 3},
                            {0, 1, 2}
                         };
typedef unsigned short int UInt16;

int bsearch(UInt16 rs, UInt16 cs, UInt16 rd, UInt16 cd, UInt16 row, UInt16 col, UInt16 k)
{
    if(k == 1)
    {
        return map[row][col];
    }
    else
    {
        UInt16 mr, mc, pr;
        mr = (rs + rd) / 2;
        mc = (cs + cd) / 2;
        if (row <= mr) //bottom
        {
            if(col <= mc) //left
            {
                return bsearch(rs, cs, mr, mc, col, row, k-1);
            }
            else //right
            {
                pr = bsearch(rs, mc, mr, cd, max_index[k-1] - (col - mc)  + 1, max_index[k-1] - row + 1, k-1);
                return max_lvl[k-1] * 3 + 3 + pr;
            }
        }
        else //top
        {
            if(col <= mc) //left
            {
                return max_lvl[k-1] + 1 + bsearch(mr, cs, rd, mc, row - mr + 1, col, k-1);
            }
            else //right
            {
                return max_lvl[k-1] * 2 + 2 + bsearch(mr, mc, rd, cd, row - mr + 1, col - mc + 1, k-1);
            }
        }
    }
}

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

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

    fscanf(f, "%hu%hu%hu", &k, &x, &y);

    if(k == 1)
    {
        fprintf(g, "%u", map[y][x]);
    }
    else
    {
        int r = bsearch(1, 1, max_index[k], max_index[k], y, x, k);
        fprintf(g, "%u", r);
    }

    fclose(f);
    fclose(g);

    return 0;
}