p312 드래곤 커브

#include<iostream>

using namespace std;

long long length[51];

void precalc()

{

length[0] = 1;

for(int i = 1; i<=50; i++)

{

length[i] = length[i-1]*2 +2;

}

}

const string X = "X+YF";

const string Y = "FX-Y";

char expand(const string& dragonCurve, int generations, int skip)

{

if(generations == 0)

{

return dragonCurve[skip];

}

for(int i = 0 ; i  < dragonCurve.size(); i++)

{

if(dragonCurve[i] == 'X' || dragonCurve[i] =='Y'){

if(skip>=length[generations])

skip -= length[generations];

else if(dragonCurve[i] == 'X')

{

return expand(X, generations-1, skip);

}

else if(dragonCurve[i] =='Y')

{

return expand(Y, generations-1,skip);

}

}

else if(skip>0)

--skip;

else

return dragonCurve[i];

}

return '#';

}

int main()

{

string t;

int C, a,b,c;

cin>>C;

precalc();

while(C--)

{

cin>>a>>b>>c;

for(int i=b; i<=b+c-1; i++)

{

string org = "FX+YF";

cout<<expand(org,a,i-1);

}

cout<<endl;

}

}