SPOJ.com - Problem ANALYSER

ANALYSER - Program Analyser

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.
The numbers during the program is running will fit in a signed 32-bit integer.
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>.
Any level 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

Note

You may try problem ANALYS_T first. It's the same problem with this one and its time limit is not so strict, but tests are easier than this problem.

Log

The time limit of this problem has been changed from 0.4/0.5 second to 1 second per test on Jun.5, 2008. All the solutions have been rejudged.

Due to compiler changes, the time limit has been shorten to 0.1 second per test.

Submit solution!

Added by:	Fudan University Problem Setters
Date:	2007-04-01
Time limit:	0.100s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: C99 ERL JS-RHINO
Resource:	Chinese National Olympiad in Informatics 2000,Day 1; translated by Blue Mary

hide comments



2024-10-27 23:49:02 Brian Bi Not sure whether the issues identified by SourSpinach were fixed, but as of now the only remaining issue is that at least some lines of input seem to end with CRLF instead of just LF (presumably from Windows), so just watch out for that.
2020-07-02 22:24:24 Simes Damn TLE! Passed tutorial version in 0.2s, and read the description here saying 1 second per test - didn't notice the real time limit was 0.1s. Sigh. ==(Problem Setter)==> After compiler changes in 2014 (or 2015? I'm not sure) the time limit has been shorten. BTW, the tests of problem ANALYS_T is easier than this problem, so it doesn't mean your solution is correct when your solution passes that problem. [Simes] Did you clarify the description of the tutorial or did I misread it? I understood it to mean the tutorial was the same problem, but with a longer time limit, i.e. the same test data too. ==(Problem Setter)==> It's my fault. I forget to mention that the tests of ANALYS_T is easier in the problem description of that problem. I've slightly modified the resource section of that problem. Last edit: 2020-07-08 02:53:19
2014-11-16 07:11:53 Jacob Plachta It seems that there's some issue with the input (in particular, with the format of a "goto" line). However, reading entire tokens instead of parsing each line character-by-character worked out...
2010-08-05 15:31:05 :D Are levels guaranteed to be distinct? AUTO RE: I guess yes. Last edit: 2012-11-26 20:08:47