Mejor Paréntesis


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, BrainF***, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

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 s(A) entonces \("(A)"\) tiene puntaje 2*s(A); y si \("A"\) y \("B"\) tienen puntajes s(A) y s(B), respectivamente, entonces \("AB"\) tiene puntaje s(A)+s(B). 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 N (2 \leq N \leq 100,000), ayude a Jorge a calcular su puntaje.

FORMATO DE ENTRADA:

  • Línea 1: Un solo entero: N

  • Líneas 2..N + 1: La línea i+1 contendrá un entero: 0 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

There are no comments at the moment.