Time Limit: 2 Seconds
Memory Limit: 65536 KB
Tomato Automata are small cool programs. You give them an infinite sequence of ones and zeros, and
they give you a sequence of numbers. They are widely used in the Stanescu Operating System (SOS).
They are written in Tomato Programming Language that is very simple. Here is its specification, tutorial
- Tomato is a very simple but powerful language.
- Lines in a Tomato program are numerated with integers from 1 to N (N100000) in the order
they appear in the input.
- There is exactly one command on a line.
- The execution starts from the first line.
- There are exactly five Tomato commands - ifgo, jump, pass, loop, and die.
- When executed, each command prints its line number (into the output sequence).
- The ifgo command has one argument - the line number of another instruction. It reads one
bit from the input stream. If the bit is one, the execution jumps to the line with the given as
argument line number. Otherwise the execution continues with the next line.
- The jump command has one argument - the line number of another instruction. When
executed, the execution jumps to the line with the given line number.
- The pass command has no arguments. It does nothing (except printing its line number like all
other commands). Then the execution continues with the next line.
- The die command has no arguments. It terminates the execution of the program (printing its
line number before that). The die command can not be used inside a loop.
- The loop command is the only one with two arguments. It may be used to construct loops.
The first argument is the starting line number (less than the line number of the loop
command), and the second is a positive integer . When executed, it loops from the
start line a <count>-1 number of times (because it is already executed once). When the loop
is executed the given number of times, the execution continues with the next line.
- The jump and ifgo commands must be used only with line numbers in the scope of the
innermost loop containing them (they can not jump outside of the innermost loop or inside
loops nested in the innermost loop that does not contain the command).
- The loop command can not be used to create overlapping loops. Nested loops must be strictly
nested (they can not use the same starting line).
- When the last line of the program is executed, the execution continues from the first except
when the last line is die command.
- White spaces may occur freely before or after the command name and their arguments.
- The maximal length of a line in Tomato Programming Language is 80 characters including
Stanescu has lots of Tomato programs. He is interested in maximal length of output sequence that
specific program can generate, where the length is the number of printed line numbers. Obviously, it is
not possible to test each possible input sequence (of ones and zeros), so he needs a program that
The input contains several programs, separated with an empty line. Each of them is a correct Tomato
For each given program your solution has to print on a separate line the maximal length of
the output sequence the program could generate. Print infinity if there is no maximal length for the
output sequence. When finite, the maximal length will not exceed 109.
loop 1 3
loop 2 2
loop 1 2
Source: Southeastern Europe 2005