Ir al contenido (saltar navegación)

Inserción de paréntesis

Tiempo máximo: 1,000-2,000 sMemoria máxima: 4096 KiB

Sea un alfabeto Σ = {a, b, c} con la siguiente "tabla de multiplicación" (donde cada fila corresponde al símbolo izquierdo y cada columna al derecho; por ejemplo, ab = b, ba = c, etc.):

abc
abba
bcba
cacc

Nótese que dicha multiplicación no es asociativa ni conmutativa.

Dada una cadena x = x1 x2 … xn de caracteres de Σ, queremos determinar si es posible insertar paréntesis en x de forma que el valor de la expresión resultante sea a. Por ejemplo, si x = bbbba, la respuesta debe ser dado que (b(bb))(ba) = (bb)c = bc = a.

Entrada

La entrada está compuesta por diversos casos de prueba, siendo cada uno de ellos una cadena de entre 1 y 100 caracteres del alfabeto Σ.

Salida

Para cada caso de prueba se debe escribir SI si es posible insertar paréntesis para conseguir una a y NO en caso contrario.

Entrada de ejemplo

bbbba
bacb
abccba

Salida de ejemplo

SI
NO
SI