HCI '16 - lvm_ex

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.5s
Memory limit: 32M

Authors:
Problem types

Remember the problem lvm from NOI 2008? With the recent advancements in computing technology, virtual machines now generally run at a much faster speed. Although the Lombok Virtual Machine was state-of-the-art technology then, its slow computing speed, as well as small limits for stack and integer sizes, has made it virtually unusable by the modern user.

Unfortunately, Squeaky the Rat had written many programs in the Lombok programming language back in its heyday, and porting those programs to another language is a very tedious task. Squeaky has tasked you to upgrade the Lombok Virtual Machine, so that his programs can be run faster and with larger constraints.

Help him make a faster version of the Lombok Virtual Machine which will work with the following constraints instead:

  • The stack does not grow bigger than 50\,000 elements
  • Every element in the stack will always have a value between -10^9 and 10^9 inclusive
  • The input program contains no more than 50\,000 instructions

Constraints

Subtask 1 [1%]

At most 40\,000\,000 instructions are executed before the program terminates.

Subtask 2 [9%]

At most 200\,000\,000 instructions are executed before the program terminates.

Subtask 3 [90%]

At most 2\,000\,000\,000 instructions are executed before the program terminates.

Sample Input

14
PUSH 5
STORE
LOAD
LOAD
PUSH -1
PLUS
STORE
LOAD
IFZERO 13
LOAD
TIMES
PUSH 0
IFZERO 3
DONE

Sample Output

120

Comments

There are no comments at the moment.