ANALYS_T - Program Analyser (tutorial)

Input

A Program which has the following format:

<Program>::=<sentence><line break>{<sentence><line break>}
<setence>::=<level><space><body>
<body>::=<addition> | <output> | <goto> | <condition> | <end>
<addition>::=<variable>+<integer>
<output>::=<variable>?
<goto>::=GO<space><level>
<condition>::=IF<space><variable>=<integer><space><goto>
<end>::=END
<variable>::=<character>
<level>::=<integer>
<integer>::=<digit>{<digit>}
<character>::=A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
<digit>::= 0|1|2|3|4|5|6|7|8|9
<line break>::=(ASCII 10)
<space>::=(ASCII 32)

The program runs following the following rules:

  • Program starts from the sentence whose level is minimum, and executed by the level from low to high except that the sentence is<goto>or<condition>.
  • All variables are initialized to 0.
  • <Addition>means<variable>+=<integer>in C++.
  • <output>means write the value of<variable>to the output file(we aren't interesting about the real output file.)
  • <condition>means if and only if the value of the <variable> equals to <integer>, <goto> will be executed, otherwise the next sentence executed is as usual.
  • After<goto>, the next sentence executed is the sentence with level which equals to the level in<goto>.
  • Program terminates by itself when <end> is executed.
  • This program can deal with all the signed 32-bit integers.
  • The number of sentences in the program is not more than 100.
  • The length of each line in the input file is not more than 20.
  • The input is correct.
  • The sentence with the maximum level is always <end>.
  • The levels is not more than 3000.

Input terminate by EOF.

Output

Output the number of sentences executed.If the program can not terminate by itself,output -1.

Example

Input:
10 A+1
20 IF A=5 GO 60
60 END
30 A+2
40 A?
50 GO 20

Output:
11

Hint:
10->20->30->40->50->20->30->40->50->20->60

Added by:Fudan University Problem Setters
Date:2008-01-02
Time limit:30s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL GOSU JS-RHINO
Resource:a copy of ANALYSER problem with 30s time limit and 1 large test case

hide comments
2012-12-09 13:24:49 Omar Soto
How far is possible to optimize the execution of a program that accomplish this using JAVA?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.