1175B.md (2378B)
1 Source: https://codeforces.com/problemset/problem/1175/B 2 3 B. Catch Overflow! 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a function $f$ written in some basic language. The function accepts an integer value, which is immediately written into some variable $x$. $x$ is an integer variable and can be assigned values from $0$ to $2^{32}-1$. The function contains three types of commands: 22 23 * for $n$ — for loop; 24 * end — every command between "for $n$" and corresponding "end" is executed $n$ times; 25 * add — adds 1 to $x$. 26 27 After the execution of these commands, value of $x$ is returned. 28 29 Every "for $n$" is matched with "end", thus the function is guaranteed to be valid. "for $n$" can be immediately followed by "end"."add" command can be outside of any for loops. 30 31 Notice that "add" commands might overflow the value of $x$! It means that the value of $x$ becomes greater than $2^{32}-1$ after some "add" command. 32 33 Now you run $f(0)$ and wonder if the resulting value of $x$ is correct or some overflow made it incorrect. 34 35 If overflow happened then output "OVERFLOW!!!", otherwise print the resulting value of $x$. 36 37 Input 38 39 The first line contains a single integer $l$ ($1 \le l \le 10^5$) — the number of lines in the function. 40 41 Each of the next $l$ lines contains a single command of one of three types: 42 43 * for $n$ ($1 \le n \le 100$) — for loop; 44 * end — every command between "for $n$" and corresponding "end" is executed $n$ times; 45 * add — adds 1 to $x$. 46 47 Output 48 49 If overflow happened during execution of $f(0)$, then output "OVERFLOW!!!", otherwise print the resulting value of $x$. 50 51 Examples 52 53 Input 54 55 ``` 56 9 57 add 58 for 43 59 end 60 for 10 61 for 15 62 add 63 end 64 add 65 end 66 ``` 67 68 Output 69 70 ``` 71 161 72 ``` 73 74 Input 75 76 ``` 77 2 78 for 62 79 end 80 ``` 81 82 Output 83 84 ``` 85 0 86 ``` 87 88 Input 89 90 ``` 91 11 92 for 100 93 for 100 94 for 100 95 for 100 96 for 100 97 add 98 end 99 end 100 end 101 end 102 end 103 ``` 104 105 Output 106 107 ``` 108 OVERFLOW!!! 109 ``` 110 111 Note 112 113 In the first example the first "add" is executed 1 time, the second "add" is executed 150 times and the last "add" is executed 10 times. Note that "for $n$" can be immediately followed by "end" and that "add" can be outside of any for loops. 114 115 In the second example there are no commands "add", thus the returning value is 0. 116 117 In the third example "add" command is executed too many times, which causes $x$ to go over $2^{32}-1$.