Fygon#7617

Fygon

1 segundo

128 megabytes

Muy difícil

Frederick es un joven programador. Participa en todas las competencias de programación que puede encontrar y siempre programa en su lenguaje de programación favorito, Fygon. Desafortunadamente, a menudo obtiene el veredicto Time Limit Exceeded, incluso cuando su algoritmo es asintóticamente óptimo. La razón es que el intérprete de Fygon es muy lento. Sin embargo, Frederick ama tanto Fygon que recurre a optimizaciones no asintóticas para que sus soluciones entren en el límite de tiempo. Para facilitarse la tarea, te pide que escribas un programa que calcule la cantidad exacta de operaciones que realiza su programa en Fygon.

Para simplificar, supongamos que en Fygon solo existen dos tipos de instrucciones. La primera es lag, que puede reemplazar casi cualquier otra instrucción. La segunda es el bucle for:

for <variable> in range (<limit>):
    <body>

Aquí <variable> toma todos los valores desde $0$ hasta <limit> - $1$ . En Fygon, <variable> es una letra latina minúscula de la $a$ a la $z$ , y <limit> es ya sea una variable <variable> definida previamente, o una constante entera positiva. El cuerpo del bucle <body> se escribe con una sangría de cuatro espacios y contiene al menos una instrucción.

El programa recibe los datos de entrada en la variable $n$ . Esta variable tiene un significado especial y no puede usarse como variable de bucle.

Tu tarea es encontrar una fórmula que exprese la cantidad de operaciones lag realizadas por un programa Fygon dado, en función de $n$ .

Entrada

Contiene un programa en Fygon. Ningún par de bucles utiliza la misma variable como contador. Cada variable utilizada dentro de range es ya sea $n$ , o una variable declarada en uno de los bucles externos.

El programa contiene a lo sumo $20$ instrucciones, de las cuales a lo sumo $6$ son bucles. Todas las constantes enteras se encuentran en el rango de $1$ a $9$ inclusive.

Salida

Muestra la fórmula para la cantidad de operaciones lag ejecutadas en función de $n$ . La longitud de la fórmula no debe exceder los $100$ caracteres (sin contar los espacios), y la fórmula debe ajustarse a la siguiente gramática:

<Expression> ::= <Product> (('+' | '-') <Product>)*
<Product>    ::= <Value> ('*' <Value>)*
<Value>      ::= 'n' | <Number> | '-' <Value> | '(' <Expression> ')'
<Number>     ::= ['0'..'9']+ ('/' ['0'..'9']+)?

Ejemplos

Ejemplo 1