TopCoder SRM 615 Div1 Easy AmebaDiv1

問題

アメーバに、n個のえさを順に与える。
i番目のえさがアメーバと同じ大きさのとき必ず、かつそのときに限りアメーバはi番目のえさを食べる。
食べなかったえさはそのときすぐに捨てられる。
えさを食べるとアメーバは大きさが倍になる。


最初アメーバの大きさは正の整数である。
全てのえさを与え終えたあと、アメーバの大きさとしてありえない正の整数の個数を求めよ。

制約条件

n≦50
えさの大きさは10^9以下の正の整数

方針

i番目のえさの大きさをX[i]とする。
X[i]に含まれない数字の大きさで開始するとアメーバは終了までその大きさ。


X[i]に含まれない数字で終了することは必ずできるので、
X[i]に含まれる数字で終了できるものの個数を数えて引ければよいということがわかる。
開始はX[i]に含まれる数字だけ試せばいい。

class AmebaDiv1 {
	public:
	int count(vector <int> X) {
		int n = X.size();
		set<int> xs(all(X));
		set<int> ok;
		
		rep(i, n){
			int c = X[i];
			
			rep(j, n) if(X[j] == c) c *= 2;
			if(xs.count(c)) ok.insert(c);
		}
		return (int)xs.size() - (int)ok.size();
	}
};