Codeforces #269 Div2 C. MUH and House of Cards

CF269に参加。
ちょっと遅れたけどABCDを解いてそこそこの順位。
http://codeforces.com/contest/471/problem/C

問題

N枚のカードが与えられる。
これを問題文の図のように積み重ねて建物の形を作っていく。
N枚のカードで過不足なく高さHの建物が作れるようなHは何通りあるか答えよ。

解法

高さHの建物に必要な最小カード枚数は2*H+3*(1+2+3+...+(H-1))=2*H+3*H*(H-1)/2である。
また、余ったカードが3の倍数なら1段目に3枚ずつ追加していけばよい。

よってHを総当たりし、条件を満たすものを数え上げればよい。

ll N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	
	ll ret=0;
	for(ll h=1;;h++) {
		ll mi=2*h+3*h*(h-1)/2;
		if(mi>N) break;
		if((N-mi)%3==0) ret++;
	}
	
	cout << ret <<endl;
	
}

まとめ

本番これはわりとすんなり解けた。