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); } };