Cod sursa(job #2614866)

Utilizator sebimihMihalache Sebastian sebimih Data 12 mai 2020 19:30:13
Problema Fractal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int LiniiPerCadran[20]; // [@Ordin] = @cate linii sunt pe cadran

void CalculeazaLiniiPerCadran()
{
	LiniiPerCadran[1] = 3;
	for (int i = 2; i <= 18; i++)
	{
		LiniiPerCadran[i] = LiniiPerCadran[i - 1] * 4 + 3;
	}
}

int CurbaHilbert(int Ordin, int Linia, int Coloana)
{
	if (Ordin == 1)
	{
		if (Linia == 0 && Coloana == 0)
		{
			return 0;
		}
		else if (Linia == 1 && Coloana == 0)
		{
			return 1;
		}
		else if (Coloana == 1 && Linia == 1)
		{
			return 2;
		}
		else
		{
			return 3;
		}
	}

	int mid = 1 << (Ordin - 1);

	if (Linia < mid && Coloana < mid)
	{
		// patratul 1
		return CurbaHilbert(Ordin - 1, Coloana, Linia);
	}
	else if (Linia >= mid && Coloana < mid)
	{
		// patratul 2
		Linia -= mid;
		return LiniiPerCadran[Ordin - 1] + 1 + CurbaHilbert(Ordin - 1, Linia, Coloana);
		
	}
	else if (Linia >= mid && Coloana >= mid)
	{
		// patratul 3
		Linia -= mid;
		Coloana -= mid;
		return 2 * LiniiPerCadran[Ordin - 1] + 2 + CurbaHilbert(Ordin - 1, Linia, Coloana);
	}
	else
	{
		// patratul 4
		// Centram
		Coloana -= mid;

		// Il transformam intr-un patrat de tipul 1
		Linia = (1 << (Ordin - 1)) - 1 - Linia;
		Coloana = (1 << (Ordin - 1)) - 1 - Coloana;

		// Pt patratul de tipul 1 => inversa linia si coloana
		return 3 * LiniiPerCadran[Ordin - 1] + 3 + CurbaHilbert(Ordin - 1, Coloana, Linia);
	}
}

int main()
{
	int k, x, y;
	fin >> k >> x >> y;
	x--; y--;
	
	CalculeazaLiniiPerCadran();

	// CITIRE: COLOANA SI DUPA LINIA
	fout << CurbaHilbert(k, y, x);
}