TopCoder Open 2010 Round 2 Medium RepresentableNumbers

問題

整数Aの各桁が全て奇数のとき、Aを"totally odd"と呼ぶことにする。
更に、"totally odd"の数二つの和で表現できる数を"representable"と呼ぶ。

与えられた数xに対し、x以上で最小のrepresentableな数を求めよ。
x≦10^8を満たす。

解法

最下位の数が奇数ならrepresentableではない。
0,1が出てきたら次の桁に繰り上がってないとおかしい。(奇数+奇数は2以上なので)

よって(残りの桁の部分)-1を再帰で呼び出してrepresentableかどうか判定すればよい。

ソースコード

bool tood(int n){
	for(;n;n/=10)if(n%10%2==0)return 0;
	return 1;
}
bool repr(int x)
{
	if(x%2!=0)return 0;
	for(;x;x/=10)
	{
		if(x%10==0||x%10==1)
		{
			x/=10; x--;
			return tood(x)||repr(x);
		}
	}
	return 1;
}

class RepresentableNumbers {
	public:
	int getNext(int X) 
	{
		for(;;X++)if(repr(X))return X;
		return -1;
	}

本番中に気づけるようになりたい。頭わるい。