Cod sursa(job #2433313)

Utilizator Mihai7Gheoace Mihai Mihai7 Data 26 iunie 2019 19:50:50
Problema Fractal Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <fstream>
#include <vector>

using namespace std;

class Solution {
	int k;
	int x;
	int y;
	int ans;
 public:
	void readData() {
		ifstream f("fractal.in");
		f >> k >> x >> y;
	}

	/*
	   2^k-1 |
	-------------------
	         |
	*/
	inline int getQuadrant(int x, int y, int half) {
		if (x > half) {
			if (y > half) {
				return 3;
			}
			else {
				return 2;
			}
		} else {
			if (y > half) {
				return 0;
			}
			else {
				return 1;
			}
		}
	}

	int getNrSteps()
	{
		if (k == 1)
		{
			if (x == 1 && y == 1)
				return 0;

			if (x == 1 && y == 2)
				return 3;

			if (x == 2 && y == 1)
				return 1;

			return 2;
		}

		int half = (1 << (k - 1));
		int q = getQuadrant(x, y, half);

		if (x <= half && y <= half)
		{
			--k;
			swap(x, y);
			return getNrSteps();
		}

		if (x > half && y <= half)
		{
			--k;
			x -= half;
			return half * half + getNrSteps();
		}

		if (x > half && y > half)
		{
			--k;
			x -= half;
			y -= half;
			return half * half * 2 + getNrSteps();
		}

		if (x <= half && y > half)
		{
			--k;
			x = 2 * half - y + 1;
			y = half - x + 1;
			return half * half * 3 + getNrSteps();
		}
	}

	inline void sol() {
		// reduce to the appropiate square
		/*int half = 1 << (k - 1);
		while (half >= 2 && x <= half && y <= half) {
			half >>= 1;
			--k;
		}*/

		ans = getNrSteps();
	}

	void printInt() {
		ofstream g("fractal.out");
		g << ans;
	}
};

int main() {
	std::ios_base::sync_with_stdio(false);
	Solution solution;
	solution.readData();
	solution.sol();
	solution.printInt();
}