問題
http://topcoder.bgcoder.com/print.php?id=1036
一辺が2^Nからなるセルの集合が与えられる。
セルの値は左上の0から始まり、ｚを描くように１ずつ増えていく。
N=1 のとき
0 1
2 3
N=2のとき
0 1 4 5
2 3 6 7
8 9 12 13
10 11 14 15
Nと行番号、列番号(r,c)が与えられた時、
その(r,c)にある数字を求める。
解き方
Nから1までセルを４等分していって、どの位置にあるかを特定していけばよい。
N=2の例を場合に考える。
move=2^(N-1)=2とすると、
rもcもmove未満のときは左上、cのみmove以上のときは右上、
rのみmove以上のときは左下、そうでなければ右下の位置になる。
また、score=4^(N-1)=4とすると、
右上のときは＋score、左下のときは+score*2、右下のときは+score*3してあげればよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class ZCurve {
public: int zValue(int N_, int r, int c) {
int ret=0;
for(int n=N_;n>=1;n--){
int move=max(1,(int)pow(2,n-1)),score=max(1,(int)pow(4,n-1));
if(r<move&&c>=move)ret+=score;
else if(r>=move&&c<move)ret+=score*2;
else if(r>=move&&c>=move)ret+=score*3;
if(r>=move)r-=move;
if(c>=move)c-=move;
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class ZCurve {
public: int zValue(int N_, int r, int c) {
int ret=0;
for(int n=N_;n>=1;n--){
int move=max(1,(int)pow(2,n-1)),score=max(1,(int)pow(4,n-1));
if(r<move&&c>=move)ret+=score;
else if(r>=move&&c<move)ret+=score*2;
else if(r>=move&&c>=move)ret+=score*3;
if(r>=move)r-=move;
if(c>=move)c-=move;
}
return ret;
}
};