USACO 2017 US Open Contest, Platinum
Problem 3. COWBASIC
Contest has ended.
Log in to allow submissions in analysis mode
COWBASIC is a simple, elegant language. It has two key features: addition and MOO loops. Bessie has devised a clever solution to overflow: all addition is done modulo 109+7. But Bessie's real achievement is the MOO loop, which runs a block of code a fixed number of times. MOO loops and addition can, of course, be nested.
Given a COWBASIC program, please help Bessie determine what number it returns.
INPUT FORMAT (file cowbasic.in):
You are given a COWBASIC program at most 100 lines long, with each line being at most 350 characters long. A COWBASIC program is a list of statements.There are three types of statements:
<variable> = <expression>
<literal> MOO {
<list of statements>
}
RETURN <variable>
There are three types of expressions:
<literal> <variable> ( <expression> ) + ( <expression> )
A literal is a positive integer at most 100,000.
A variable is a string of at most 10 lowercase English letters.
It is guaranteed that no variable will be used or RETURNed before it is defined. It is guaranteed that RETURN will happen exactly once, on the last line of the program.
OUTPUT FORMAT (file cowbasic.out):
Output a single positive integer, giving the value of the RETURNed variable.Scoring
- In 20 percent of all test cases - MOO loops are not nested.
- In another 20 percent of all test cases - The program only has 1 variable. MOO loops can be nested.
- In the remaining test cases, there are no further restrictions.
SAMPLE INPUT:
x = 1
10 MOO {
x = ( x ) + ( x )
}
RETURN x
SAMPLE OUTPUT:
1024This COWBASIC program computes 210.
SAMPLE INPUT:
n = 1
nsq = 1
100000 MOO {
100000 MOO {
nsq = ( nsq ) + ( ( n ) + ( ( n ) + ( 1 ) ) )
n = ( n ) + ( 1 )
}
}
RETURN nsq
SAMPLE OUTPUT:
4761This COWBASIC program computes (105∗105+1)2 (modulo 109+7).
Problem credits: Jonathan Paulson