SRM553 Div1 Easy - Suminator

問題

suminatorという装置がある
この装置には最初無限に0が詰まったスタックが入っており、長さnの非負整数のみからなる数列aを入れると、
1) 数列aの各要素を手前から1個ずつ見ていき、a[i]が0のときはスタックから2個取り出してそれらの和をスタックに入れ、a[i]が0でないときはa[i]をスタックに入れる
2) スタックから1個取り出してその値を出力する
という操作をする

1つの要素だけ-1になっていて他は全て非負整数の数列aと非負整数xが与えられる
-1を好きな非負整数pに変えて、suminatorにaを入れるとxが出力されるようにしたい
これが可能な場合はpの最小値を、不可能な場合は-1を返せ

1 <= n <= 50
-1 <= a[i] <= 10^9
1 <= x <= 10^9

解法

まずp=0を試してみる
それでxにならなかったらp=1とp=2を試してみる
p=1のときのsuminatorの出力をv、p=2のときをuとする
suminatorは非負整数の足し算しか行わないから、uとvの関係としては
1) v=u (pの値がsuminatorの結果に影響しない場合)
2) u=v+1 (そうでない場合)
という2通りしかあり得ない
1)の場合はv=xならreturn 1、そうでなければreturn -1
2)の場合はvが既にxを超えていたらpとして適切な値は存在しないからreturn -1、そうでなければreturn 1+x-v

class Suminator {
public:
	ll sumi(vector<int> &a) {
		stack<ll> st;
		each(i,a) {
			if (i!=0) st.push(i);
			else if (st.size()>=2) {
				ll a = st.top(); st.pop();
				ll b = st.top(); st.pop();
				st.push(a+b);
			}
		}
		return (st.empty() ? 0 : st.top());
	}

	int findMissing(vector<int> a, int x) {
		int id = find(all(a),-1) - a.begin();
		a[id] = 0;
		if (sumi(a)==x) return 0;
		a[id] = 1;
		ll v = sumi(a);
		a[id] = 2;
		ll u = sumi(a);
		if (v==u) return (v==x ? 1 : -1);
		return (x<v ? -1 : 1+x-v);
	}
};