|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
III Copa UHEnded |
Para este problema, vamos a definir una expresión regular recursivamente de la siguiente manera:
- Un solo carácter $\$$ es una expresión regular que acepta la cadena vacía.
- Caracteres individuales como por ejemplo 'a', 'b' y 'c' son expresiones regulares que aceptan cadenas "a", "b" y "c",
respectivamente. - Si $P$ es una expresión regular, $(P)$ es también una expresión regular que acepta todas las cadenas aceptadas por P.
- Si $P$ es una expresión regular que es un resultado directo de aplicar cualquiera de las reglas $1-4$, su iteración, denotado como $P*$, es también una expresión regular que acepta cadenas de la forma $s = u_1 u_2 \ldots u_k$ (la concatenación de cero o más cadenas) donde $k$ es cualquier entero no negativo y cada cadena $u_i$ es aceptada por $P$.
- Si $P$ y $Q$ son expresiones regulares que son resultados directos de la aplicación de cualquiera de las reglas $1-5$, su
concatenación, denotado simplemente como $PQ$, es también una expresión regular que acepta cadenas de la forma
$s = uv$ (una concatenación de $u$ y $v$, cada una de las cuales puede estar vacía) donde el prefijo $u$ es aceptado
por $P$ y el sufijo $v$ es aceptado por $Q$. - Si $P$ y $Q$ son expresiones regulares que son resultados directos de la aplicación de cualquiera de las reglas $1-6$, su
unión, denotada como $P | Q$, es también una expresión regular que acepta ambas, cadenas aceptadas por $P$ y cadenas aceptadas por $Q$.
Las restricciones en las reglas $4-6$ son impuestas para evitar ambigüedades y priorizar operaciones: al leer una expresión regular, evalúe iteración, luego concatenación, luego unión. Los paréntesis desempeñan el papel habitual de priorizar las operaciones encerradas en ellos.
Dada una expresión regular $r$, encuentre la cadena más corta $s$ que es aceptada por esta expresión regular $r$. Si hay varias cadenas de este tipo imprima la menor en orden lexicográfico.
Input
Cada descripción del caso de prueba consta de una expresión $r$ que es una cadena construida por las reglas anteriores. Su longitud es de $1$ a $500$ caracteres.
Output
Para cada caso de prueba, imprima una sola línea que contenga la cadena más corta aceptada por la expresión regular dada
$r$. Si hay más de una cadena, imprima la más pequeña lexicográficamente. Si la respuesta es una cadena vacía, imprima un solo carácter $\$$.
$r$. Si hay más de una cadena, imprima la más pequeña lexicográficamente. Si la respuesta es una cadena vacía, imprima un solo carácter $\$$.
Sample test(s)
Input
1
a
Output
a
Input
13
ab|ac*(ca|cb)
Output
ab
Input
11
((ab|ac)a)*
Output
$