Pagini recente » Cod sursa (job #1379894) | Cod sursa (job #1432158) | Cod sursa (job #2103890) | Cod sursa (job #18218) | Cod sursa (job #2432989)
#include <fstream>
#include <vector>
using namespace std;
class Solution {
int k;
int x;
int y;
int ans;
vector<int> lastSquare;
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;
}
}
}
inline void perm0(vector<int>& v) {
swap(v[1], v[3]);
};
inline void perm1(vector<int>& v) {
swap(v[0], v[2]);
}
inline void perm2(vector<int>& v) {
// nothing
}
inline void perm3(vector<int>& v) {
// nothing
}
void recursive() {
int half = 1 << (k - 1);
if (x > 2 || y > 2) {
int cad = getQuadrant(x, y, half);
switch (cad) {
case 0:
ans += 3 * (half << 1);
if (x > 2) {
x = x - half; // redundant code to avoid memory jumps
}
if (y > 2) {
y = y - half;
}
recursive();
perm0(lastSquare);
break;
case 1:
// ans += 0 * ...;
if (x > 2) {
x = x - half; // redundant code to avoid memory jumps
}
if (y > 2) {
y = y - half;
}
recursive();
perm1(lastSquare);
break;
case 2:
ans += (half << 1);
if (x > 2) {
x = x - half; // redundant code to avoid memory jumps
}
if (y > 2) {
y = y - half;
}
recursive();
perm2(lastSquare);
break;
case 3:
ans += half << 2; // 4 * half
if (x > 2) {
x = x - half; // redundant code to avoid memory jumps
}
if (y > 2) {
y = y - half;
}
recursive();
perm3(lastSquare);
break;
}
}
}
void getNrSteps() {
/*
while(x/2 != 1) {
sol += 3 | 2 | 1 * pow(2, k);
}
sol += 3 | 2 | 1 | 0;
la final sunt 4 * 4 combinatii se pot micsora?
*/
/* lastSquare
index - quadrant index
value - value to be added to ans
*/
lastSquare.resize(4, 0);
lastSquare[0] = 3;
lastSquare[1] = 0;
lastSquare[2] = 1;
lastSquare[3] = 2;
// reduce to the appropiate square
int half = 1 << (k - 1);
while (half >= 2 && x < half && y < half) {
half >>= 1;
--k;
}
recursive();
/*
la ordinul 2 gasim ca primul |_| sta doar in doua poziti
al doilea in doar
*/
/*
pare ca fiecare poate fi gandi ca o permutare
*/
int cad = getQuadrant(x, y, 1);
ans += lastSquare[cad];
}
void printInt() {
ofstream g("fractal.out");
g << ans;
}
};
int main() {
std::ios_base::sync_with_stdio(false);
Solution solution;
solution.readData();
solution.getNrSteps();
solution.printInt();
}