Problem#
Given a function f, f is initially passed the value of x. f has three types of instructions:
for n - loop
end - the termination symbol for each loop. The code between each pair of for n and end instructions should be executed n times. Ensure that each for n instruction is paired with an end instruction.
add - increment x by 1.
After performing all the operations, x is returned as the result.
During the calculations, x may exceed $2^{32}-1$, in which case you should output OVERFLOW!!!
Now please output the value of f(0).
Approach#
At first glance, this problem seems to require the use of a stack, but I decided to use an array instead.
f[i] represents the number of times the code is executed within the ith loop,
f[i] = f[i - 1] * n
There are two points where overflow may occur: when the loop depth is too deep and when the addition is too large. However, not all deep loops necessarily have addition statements, so I'll set a flag to check for this.
I feel like I may have made it too complicated...
Code#
#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;
}