ZOJ Problem Set - 3510
There are multiple assignment expressions. Each of them is defined by the following BNFs.
Each variable is a string of uppercase letters. The rule to calculate an assignment expression is the same as in the C programming language. An assignment cannot be calculated unless all variables on the right have assigned value from previous calculation. Variable can be assigned more than once.
Now, you need to select some assignment expressions and put them in order to make sure all variables have assigned values and the sum of the final values of all variables is minimal.
Multiple test cases. For each case, the first line is the number of assignment expressions and then one expression per line.
No more than 10000 assignment expressions. No more than 2000 variables in each case. Length of variable is no more than 7. Length of each assignment expression is no more than 1000. There will always be a space beween tokens in expression. There will always be an empty line between test cases.
For each test case. Output the minimal sum of final values of all variables in the first line. Then output your selected expressions one expression per line in exact form as in the input.
If there is no possible answer or the minimal sum cannot be expressed in a unsigned 64-bit integer. Output "stupid expressions!" instead.
2 A = ( B * 2 ) B = ( A + 1 ) 7 A = 1 B = 3 C = ( ( A + B ) * A ) C = ( 2 * ( A * B ) ) C = ( ( A + ( 2 * B ) ) + A ) A = ( ( C + B ) + A ) B = ( A + 1 )
stupid expressions! 6 A = 1 B = ( A + 1 ) C = ( ( A + B ) * A )
Author: CUI, Tianyi
Contest: ZOJ Monthly, July 2011