Cod sursa(job #2375082)

Utilizator alexghitaAlexandru Ghita alexghita Data 7 martie 2019 22:10:19
Problema Fractal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.91 kb
/**
 * 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;
}