AOJ 507: Square

問題文略

模範解答では、再帰を使って解くらしいです。
最初に積み上げて置き、右側からブロックを一旦取り去って、次の状態にすることを繰り返してみました。
vectorを使ってるので(更に、push_back()とpop_back()を多用している)速くはないです。

#include <cstdio>
#include <vector>
using namespace std;

inline void output(vector<int> t){
	for(int i = 0,l = t.size(); i < l; i++){
		printf("%d",t[i]);
		if(i+1 == l) printf("\n");
		else printf(" ");
	}
}

inline bool rec(vector<int>& t){
	if(t[0] == 1) return false;
	int a,ac = 0;
	while(true){
		ac++;
		a = t.back();t.pop_back();
		if(a != 1) break;
	}
	a--;//一段下げて、その高さに揃える
	t.push_back(a);
	while(a<ac){
		t.push_back(a);
		ac -= a;
	}
	if(ac) t.push_back(ac);
	return true;
}

int main(){
	int n;
	while(scanf("%d",&n),n){
		vector<int> t;
		t.reserve(n);
		t.push_back(n);
		
		do{
			output(t);
		}while(rec(t));
	}
	return 0;
}