Autor da análise: jesusalejandro
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"
Discuta o problema
Acabo de pasar este problema voy hacer el analisis, en unos momentos.
Saludos
não sei pq ainda tomo WA nesse problema….
Essas entradas do Jesus por exemplo funcionam bem.
caramba ta acontecendo coisa de louco aqui… eu tenho uma cadeia de chars global char s[310] que leio a entrada, e não altero em lugar algum…
Dentro da recursão é como se essa cadeia de caracteres estivesse misteriosamente vazia. e ainda o programa acerta essas respostas hehehe…
como era de se esperar tinha um erro meu…. tinha outra cadeia de nome s no main (e olha q eu ja tinha procurado uma vez =P).
Mas o mais louco é que o programa daquele jeito respondia 42 pro ABABABABABA e certo tb para as outras
Probe con, "ABABABABABC" resposta es "0", isso quere decir que a ultima letra tem que ser igual tambem para poder particionar.
Dava problema nesse tipo de caso mesmo, mas porque eu lia em uma string do main e resolvia em uma outra que eu nem mexia….
Agora deu AC.
Obrigado.