Cod sursa(job #3031074)

Utilizator anamariatoaderAna Toader anamariatoader Data 18 martie 2023 15:22:47
Problema Fractal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

void compute_fractal_sizes(int *fract, int k)
{
    fract[1] = 3;
    for (int i = 2; i <= k; i++)
        fract[i] = 4 * fract[i-1] + 3;
}

int hilbert(int k, int x, int y, int *fract)
{
    if (k == 1) {
        if (!y) return x;
        else return 3 - x;
    }

    int half = (1 << (k-1));

    // upper left
    if (x < half && y < half)
        return hilbert(k-1, y, x, fract);
    
    // lower left
    if (y < half)
        return fract[k-1] + 1 + hilbert(k-1, x - half, y, fract);

    // upper right
    if (x < half)
        return 3 * fract[k-1] + 3 + hilbert(k-1, half - 1 - (y - half), half - 1 - x, fract);

    // lower right
    return 2 * fract[k-1] + 2 + hilbert(k-1, x - half, y - half, fract);
}

int main()
{
    ifstream fin("fractal.in");
    ofstream fout("fractal.out");

    int k, x, y;
    fin >> k >> y >> x;

    int *fract = (int *) malloc((k+1) * sizeof(int));
    if (!fract) return -1;

    compute_fractal_sizes(fract, k);

    int res = hilbert(k, x-1, y-1, fract);

    fout << res;

    return 0;
}