codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.