問題
http://community.topcoder.com/stat?c=problem_statement&pm=11354&rd=15175
解き方
プログラムをスタックで実行し、０，１，２で出力させ
０で出力した時に求める値と一致すれば０，
１，２を出力させた時に出力が同じで、求める答えと違えば−１，
出力が求める答えよりも小さければ差分を足すことで答えが求められる。
intでは和がフローしてしまうのでlong long型を用いる。
コード
class Suminator {
public:
long long rec(vector<int> program,int x){
stack<long long> s;
FORE(i,0,program.size()){
if(program[i]==-1)program[i]=x;
if(program[i]==0){
long long a=0,b=0;
if(!s.empty()){
a=s.top();
s.pop();
}
if(!s.empty()){
b=s.top();
s.pop();
}
s.push(a+b);
}else{
s.push(program[i]);
}
}
return s.empty() ? 0 : s.top();
}
int findMissing(vector<int> program, int wantedResult) {
if(rec(program,0)==wantedResult)return 0;
long long x=rec(program,1);
long long y=rec(program,2);
if(x==wantedResult)return 1;
if(x==y || x>wantedResult)return -1;
return wantedResult-x+1;
}
};
public:
long long rec(vector<int> program,int x){
stack<long long> s;
FORE(i,0,program.size()){
if(program[i]==-1)program[i]=x;
if(program[i]==0){
long long a=0,b=0;
if(!s.empty()){
a=s.top();
s.pop();
}
if(!s.empty()){
b=s.top();
s.pop();
}
s.push(a+b);
}else{
s.push(program[i]);
}
}
return s.empty() ? 0 : s.top();
}
int findMissing(vector<int> program, int wantedResult) {
if(rec(program,0)==wantedResult)return 0;
long long x=rec(program,1);
long long y=rec(program,2);
if(x==wantedResult)return 1;
if(x==y || x>wantedResult)return -1;
return wantedResult-x+1;
}
};