hogloidのブログ

へなちょこ

PKU3092 Non-divisible 2-3 Power Sums

数N(<=2^32-1)を
2^a*3^bの和で表せ。ただし2^a*3^bのどれかがどれかで割りきれてはいけない


探索します。メモ化しなくてもOKです
まず、nが2で割りきれるとき、すべての2^a*3^bのaはa>=1なので、
n/2の場合に帰結できます。
nが2で割りきれないとき、2^a*3^bのうち一つだけaが0のものがあるはずなので、
一つサイズを小さくできます
そんな感じ

vector<pair<int,int> > res;
int dfs(int n,int thr){
	if(n==0) return 1;
	if(n==1){
		if(thr<0) return 0;
		res.pb(mp(0,0));
		return 1;
	}
	int cnt=res.size();
	if(n%2==0){
		if(dfs(n/2,thr)){
			REPN(i,res.size(),cnt) ++res[i].fr;
			return 1;
		}
	}else{
		lint mul=1;
		REP(i,thr) mul*=3;
		for(int i=thr;i>=0;--i,mul/=3){
			if(mul>n) continue;
			if(dfs(n-mul,i-1)){
				res.pb(mp(0,i));
				return 1;
			}
		}
	}
	return 0;
}

int main(){
	int t;scanf("%d",&t);
	REP(setn,t){
		res.clear();
		int n;scanf("%d",&n);
		dfs(n,30);
		printf("%d %d",setn+1,(int)res.size());
		REP(i,res.size()) printf(" [%d,%d]",res[i].fr,res[i].sc);
		putchar('\n');
	}
	return 0;
}