PKU 2795 - Exploring Pyramids

Autor da análise: jesusalejandrojesusalejandro

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2795

Resumo

Dada una cadena de caracteres,donde cada letra de la cadena representa el color de un tunel visitado por el robot;
encontrar el numero de maneras de cuevas que cumplen con esta representacion, dada las siguientes condiciones para el recorrido:

1.Cada vez, que visita un tunel se escribe el caracter, que representa el color del tunel.

2.El robot tiene una pila, y recorrera todo el lado derecho hasta que no haya mas cuevas, y regresara mediante los caminos guardados en la pila,de ese modo ira en la direccion contraria, para recorrer el total de la cueva.

3. El recorrido termina cuando el robot regresa de las cuevas, saliendo por donde inicion el recorrido.

La respuesta sera dada con modulo 1 000000000.

Solução

-Primero darse cuenta que es un arbol , caracteristica "Padre".
-Para el ejemplo :"ABABABA".

Existen 5 cuevas que podrian ser resultado de la representacion de la cadena de caracteres.

Dica 1.-El numero total de representaciones es el producto de la representacion de cada sub-arbol.
Para este caso Raiz "A",podemos tener dos arboles "BA" y "BABA"—>lo que seria N#=Ways("ABA")*Ways("ABABA");
Pues ahora para el total de "WAYS", basta recorrer toda la cadena y sumar todos los productos.

Dica 2.-El recorrido no tiene porque ser "i++", sino i+=2; ya que sera calculo innecesario; ademas notar la condicion que el "Padre" de cada sub-cadena tiene que ser igual al de la cadena total.Con esto asegura el retorno del robot.

Dica 3.-Como se necesitara resultados ya calculados, y no volver a calcular podemos usar "Programacion Dinamica", la longitudad maxima es de 300, lo que es razonable.En mi caso hice con "Memoizen".

Testes

Entrada

A
ABA
AB
ABABABA
ABABABABABA

Saída

1
1
0
5
42

PDT:"Manhana lo pasare a Portugues"

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License