SRM 553 div1 easy Suminator

問題

TopCoder Statistics - Problem Statement

最初に十分たくさん 0 が詰まっているスタックがある。これに次のような操作をする。

• スタックに数 p を入れる
• スタックから 2 つの数 p, q を取り出し, p+q を入れる

このような操作を順番にするプログラムが数列で与えられるが, 一つの値だけ好きに決めることができる(位置は指定されている)。それに適切な値を入れることで最後にスタックの一番上に所望の値 W を残すことが可能か。可能な場合はその最小値を, 不可能な場合は -1 を出力せよ。

解法

program に 0 を入れる場合とそうでない場合だけですべての場合が尽くされます。0 の場合はそのままシミュレーションして試しましょう。

そうでない場合は, -1 のところに x を入れたとしてシミュレーションをします。最後に x+n という値がスタックの一番上に出ていたとすると, x+n = W となっていれば x = W-n とすれば良く, x+n という値がスタックの一番上にない場合は一番上の値が W と一致してれば x = 1 とすれば良いです。

class Suminator {
public:
    int findMissing(vector <int> program, int wantedResult) {
        int n = program.size();
        {
            stack<ll> st;
            for (int i = 0; i < 100; i++)
                st.push(0);
            for (int i = 0; i < n; i++) {
                if (program[i] <= 0) {
                    ll p = st.top(); st.pop();
                    ll q = st.top(); st.pop();
                    st.push(p+q);
                } else {
                    st.push(program[i]);
                }
            }
            if (st.top() == wantedResult) return 0;
        }
        {
            stack<ll> st;
            for (int i = 0; i < 100; i++) 
                st.push(0);
            int top = -1;
            for (int i = 0; i < n; i++) {
                if (program[i] == -1) {
                    top = 0;
                    st.push(0);
                } else if (program[i] == 0) {
                    top--;
                    ll p = st.top(); st.pop();
                    ll q = st.top(); st.pop();
                    st.push(p+q);
                } else {
                    st.push(program[i]);
                    top++;
                }
            }
            if (top > 0) {
                if (st.top() == wantedResult) return 1;
                else return -1;
            } else {
                ll x = wantedResult-st.top();
                if (x > 0) return x;
                else return -1;
            }
        }
    }
    };
}