Internet Problem Solving Contest

IPSC 2017

Problem H – Holy cow, Vim!

Little Johnny is attending a summer programming camp. The very first assignment was to write a program that reads a number x and prints the same number x. Johnny’s program was already working, but then an accident happened. While using the Vim editor, Johnny pressed something without paying attention and his program got turned upside down. That is, he somehow reversed the order of lines in his program.

To Johnny’s amazement, the program still worked, but now it did something different: it read x and printed x2.

Johnny tried to remember what he pressed to put the lines back in the correct order, but he made another mistake and Vim sorted the lines of his program. Johnny tried the new program and was completely lost for words: the program now read x and printed x.

“Holy cow, Vim is magic! I’ll use it until the end of my life!” exclaimed Johnny.

“That’s just because nobody knows how to exit it,” another student yelled back.

Can you write a program that behaves the same way as Johnny’s program?

Problem specification

In this problem, you’ll use a simple stack-based programming language. The memory is a stack of signed integers. Various commands push values onto the stack or pop values from the top of the stack. The stack is initially empty and may be left non-empty when the program ends.

A program consists of several lines, and each line consists of one or more commands separated by semicolons. A command can be one of the following:

The language is very strict. You cannot use any extra whitespace or semicolons or anything like that.

Only integers between −231 and 231 − 1 (inclusive) are supported. Pushing an integer outside of this range to the stack is an error.

Input specification

There is no input.

Output specification

Your task is to write a program that reads an integer x and outputs x. However, if the order of the lines of the program is reversed (i.e., the last line becomes the first line, etc.), the new program should output x2. And if the lines of the program are sorted lexicographically, it should output x.

You may assume that |x|≤30 000.

The program can have at most 1000 lines. For any valid x your program must terminate after the execution of at most 10 000 commands.

In the easy subproblem H1 each line may contain up to 1000 commands.

In the hard subproblem H2 each line may contain at most two commands.


The following program reads x and outputs x − 7.

push 7

If you reverse the order of lines of the above program, “print” will become the first command, and the program will fail because it tries to print the top of an empty stack.