問題#
関数 f が与えられます。f は最初に x の初期値を受け取ります。f にはいくつかの命令があります。命令は 3 種類あります：
for n - ループ
end - 各ループの終了記号。for nとendのペアの間のコードはn回実行されます。各for n命令に対して、対応するend命令が存在することが保証されています。
add - xを1増やします。
すべての操作が終了した後、x は戻り値として返されます。
途中の演算中に、x が $2^{32}-1$ よりも大きくなることがあります。その場合、"OVERFLOW!!!" と出力する必要があります。
今、f (0) の値を出力してください。
考え方#
一見、この問題はスタックを使う必要がありますが、私は配列を使うことにしました。
f[i]は現在の第iレベルのループで実行される回数を表します。
f[i] = f[i - 1] * n
オーバーフローが発生するのは、ループの深さが深すぎる場合と、加算が過剰な場合ですが、非常に深いループには必ずしも加算文が含まれているわけではないため、ここではフラグを立てて判定します。
自分のやり方は複雑すぎるかもしれません。。。。。。
コード#
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
using namespace std;
const long long over = ((long long)1 << 32) - 1;
int n, h;
long long x;
long long cnt = 0;
vector<long long> f;
int main (void) {
f.push_back(1);
scanf("%d", &n);
char t[4];
bool flag = 0;
for (int i = 1; i <= n; ++i) {
scanf("%s", t);
if (t[0] == 'f') {
++cnt;
f.resize(cnt + 1);
scanf("%d", &h);
if (over / h < f[cnt - 1]) {
flag = 1;
}
f[cnt] = f[cnt - 1] * h;
}
else if (t[0] == 'a') {
if (flag) {
printf("OVERFLOW!!!\n");
exit(0);
}
else {
int tmp = x;
x += f[cnt];
if (x > over || x < tmp) {
printf("OVERFLOW!!!\n");
exit(0);
}
}
}
else {
flag = 0;
--cnt;
}
}
printf("%I64d\n", x);
return 0;
}