Mejor Paréntesis
Recientemente, los concursantes han estado competiendo con cadenas de paréntesis balanceados y comparándolas entre sí para ver quién tiene la mejor.
A tales cadenas se les asigna un puntaje como sigue (todas las cadenas son balanceadas): la cadena \("()"\) tiene puntaje 1; si \("A"\) tiene puntaje entonces \("(A)"\) tiene puntaje ; y si \("A"\) y \("B"\) tienen puntajes y , respectivamente, entonces \("AB"\) tiene puntaje . Por ejemplo, \(s("(())()") = s("(())") + s("()") = 2*s("()")+1 = 2*1+1 = 3\).
Jorge quiere derrotar a todos sus compañeros concursantes, por lo tanto necesita calcular el puntaje de algunas cadenas. Dada una cadena de paréntesis balanceados de longitud , ayude a Jorge a calcular su puntaje.
FORMATO DE ENTRADA:
Línea 1: Un solo entero:
Líneas 2..N + 1: La línea contendrá un entero: si el i-ésimo carácter de la cadena es , y 1 si el i-ésimo carácter de la cadena es
FORMATO DE SALIDA:
- Línea 1: El puntaje de la cadena. Como este número puede ser bastante grande, dé el puntaje módulo 12345678910.
ENTRADA EJEMPLO
6
0
0
1
1
0
1
SALIDA EJEMPLO
3
DETALLES DE LA ENTRADA:
Esto corresponde a la cadena \("(())()"\).
DETALLES DE LA SALIDA:
Como se discutió anteriormente.
Comments