Pintando las ventanas.
Submit solution
Points:
100 (partial)
Time limit:
1.0s
Memory limit:
16M
Author:
Problem type
Allowed languages
C, C#, C++, Java, JS, Pascal, Python, VB
La gerencia de la tienda de estimulación a los azucareros del centro decidió pintar las ventanas con franjas de color blanco, azul y rojo. Ellos quieren satisfacer las siguientes condiciones:
• Franjas del mismo color no pueden ser colocadas una detrás de otra.
• Una franja azul siempre tiene que ser colocada entre una blanca y una roja o entre una roja y una blanca.
Escriba un programa que ayude a la gerencia de la tienda a contar la cantidad de formas de pintar su tienda. Como la respuesta puede ser muy larga imprímala módulo .
Entrada
La primera y única línea contiene en número , la cantidad de franjas.
Salida
En una única línea imprima la respuesta del problema módulo .
Ejemplo #1 de Entrada
3
Ejemplo #1 de Salida
4
Ejemplo #2 de Entrada
54321
Ejemplo #2 de Salida
111378255
Explicación del primer ejemplo:
Comments
Gente, ¿pueden comentarme alguna idea para este ejercicio? No entiendo muy bien cómo empezar y no sé muy bien cómo usar la exponenciación de matrices en el código. Gracias.
Espero esta idea te ayude (no me borren el comentario, es solo una idea, no la solucion):
La cantidad de franjas de tamanho que terminan en color X depende de la cantidad de franjas de tamanho que terminan en color , color ...
Muchas gracias. Funcionó. Un abrazo <3
Se puede resolver usando dp
Bonus: resuelvanlo para
:)
Me arriesgaría a decir que matrix power
Acertaste ;)
sip
.