#P18217. The Emperor
The Emperor
The Emperor
注意:本题是 The Empress 的逆版本,两题的数据限制不同。
咖波发明了一种有趣的解释型语言 Push-Pop。解释器初始有一个容量无限的空栈,并从程序的第一条指令开始执行。这种语言只有以下两种指令。
POP a GOTO x; PUSH b GOTO y
如果栈非空且栈顶元素等于 ,弹出栈顶元素,接下来执行第 条指令;否则,把元素 压入栈中,接下来执行第 条指令。
HALT; PUSH b GOTO y
如果栈为空,执行完本条指令后整个程序停机;否则,把元素 压入栈中,接下来执行第 条指令。
咖波想升级自己的简易解释器,以处理更多的指令。给定一个最多包含 条指令的程序,请计算它在停机前一共执行了多少条指令。
输入格式
第一行包含整数 ,表示程序的指令数量。
之后 行,每行包含上述两种格式之一的一条指令。指令从 到 编号。
输出格式
如果程序永远不会停机,输出 -1。
否则,输出程序执行的指令总数对 取模的结果。使程序停机的那条指令也计入总数。
数据范围
- ;
- 每条指令中,,。
样例 1
输入:
1
HALT; PUSH 1 GOTO 1
输出:
1
样例 2
输入:
5
POP 1 GOTO 2; PUSH 1 GOTO 2
HALT; PUSH 1 GOTO 3
POP 1 GOTO 4; PUSH 2 GOTO 4
POP 1 GOTO 2; PUSH 2 GOTO 4
HALT; PUSH 99 GOTO 4
输出:
5
样例 3
输入:
1
POP 1 GOTO 1; PUSH 1 GOTO 1
输出:
-1
与 The Empress 相比,本题的主要区别是:指令数量上限为 ;程序可能永远不停机,此时输出 -1;对于会停机的程序,只需输出执行指令数对 取模的结果。