Pagini recente » Cod sursa (job #2970454) | Cod sursa (job #1029962) | Cod sursa (job #2662930) | Cod sursa (job #2591865) | Cod sursa (job #2375082)
/**
* Folosim un algoritm de tip Divide et Impera pentru a calcula numărul de pași,
* pornind de la observația că o curbă Hilbert de ordin k este formată din patru
* curbe de ordin k - 1. De asemenea, observăm că numărul de pași pentru a
* parcurge complet o curbă de ordin k este 4^k.
*
* Vom folosi o funcție recursivă, care ia ca parametri ordinul curbei k și
* coordonatele punctului (x, y). Pe baza acestora, determinăm în ce cadran se
* află punctul, după care calculăm coordonatele punctului în interiorul acelui
* cadran, precum și numărul de pași necesari pentru a ajunge la acel cadran,
* iar soluția va fi acest număr de pași, plus numărul de pași returnat de
* apelul recursiv pentru cadranul de ordin k - 1.
*
* O posibilă optimizare este precalcularea puterilor lui 2 până la 2^(k - 1),
* din moment ce altfel vor fi recalculate, însă k este suficient de mic încât
* acest lucru să nu facă o diferență mare la timpul de execuție final.
*/
#include <bits/stdc++.h>
using namespace std;
// Ridică baza b la puterea e.
int power(int b, int e) {
int result = 1;
while (e) {
result *= b;
e--;
}
return result;
}
// Returnează numărul de pași pentru a ajunge la punctul (x, y) pe o curbă
// Hilbert de ordin k.
int solve(int k, int x, int y) {
if (k == 1) {
if (x == 1 && y == 1) return 0;
if (x == 1 && y == 2) return 1;
if (x == 2 && y == 2) return 2;
else return 3;
}
// Dimensiunea unui cadran (curbă de ordin k - 1)
int quad_size = power(2, k - 1);
// Numărul de pași necesari pentru a parcurge un cadran.
int quad_steps = quad_size * quad_size;
if (x <= quad_size && y <= quad_size) {
// Dacă punctul se regăsește în primul cadran, inversăm coordonatele, adică
// îi luăm simetricul față de a doua bisectoare.
return solve(k - 1, y, x);
} else if (x <= quad_size && y > quad_size) {
// Dacă punctul se regăsește în al doilea cadran, reducem y la coordonatele
// acelui cadran și adăugăm pașii necesari pentru a parcurge primul cadran.
return solve(k - 1, x, y - quad_size) + quad_steps;
} else if (x > quad_size && y > quad_size) {
// Dacă punctul se regăsește în al treilea cadran, reducem x și y la coordo-
// natele acelui cadran și adăugăm pașii necesari pentru a parcurge primele
// două cadrane.
return solve(k - 1, x - quad_size, y - quad_size) + 2 * quad_steps;
} else {
// Dacă punctul se regăsește în al patrulea cadran, îi luăm simetricul față
// de prima bisectoare și adăugăm pașii necesari pentru a parcurge primele
// trei cadrane.
return solve(k - 1, quad_size + 1 - y, 2 * quad_size + 1 - x) +
3 * quad_steps;
}
}
int main() {
stdin = freopen("fractal.in", "r", stdin);
stdout = freopen("fractal.out", "w", stdout);
int k, x, y;
int steps;
cin >> k >> x >> y;
steps = solve(k, x, y);
cout << steps;
}