Solución a "Pulseras"

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 10 **Autor: **Alain Acevedo Mejía

Considero este problema como un buen ejemplo para quienes desean comenzar a trabajar con problemas de programación dinámica. Se nos pide calcular la cantidad de pulseras diferentes que se pueden construir bajo ciertas condiciones. Podemos comenzar preguntándonos, ¿qué sucede si la primera cuenta es negra? La siguiente podrá ser sólo blanca. Y si comenzamos con una blanca, la siguiente puede ser negra o blanca. Podemos entonces en una matriz de 2xn colocar en cada columna cuántas secuencias distintas hay que en la posición i-ésima terminen en negro y cuántas en blanco de tal modo que no haya dos cuentas negras consecutivas. Simplemente, para obtener los números de la siguiente posición, observamos que el número de las que terminan en blanco es la suma de ambos números de la posición anterior y de las que terminan en negro es el número de secuencias que terminan en blanco de la posición anterior.

Resta solo un detalle más a considerar. Requerimos que la secuencia no inicie y termine en negro, pues los extremos quedarán adyacentes al cerrar la pulsera. Una forma de resolver esto es la siguiente: Contamos, con el método descrito, cuántas secuencias distintas hay que inicien con blanco y que no tengan dos cuentas negras consecutivas. El número que nos pide el problema será entonces la cantidad de pulseras que empiezan con blanco y cumplen con que no haya dos negras consecutivas (independientemente de con qué color terminen) más el número de pulseras que inicien con negro y terminen con blanco (y claro, cumplan con que no haya dos negras consecutivas). ¿Cuántas hay de estas últimas? La misma cantidad que de pulseras que inician con blanco y terminan con negro, pues su simétrica inicia con negro, termina con blanco y claramente sigue cumpliendo el que no posea dos cuentas negras consecutivas. Así que es posible resolver el problema con un código muy breve, como se muestra abajo.

Solo resta mencionar que hay que tener cuidado de aplicar el módulo correctamente. Se pueden evitar errores definiendo el valor del mismo para no tener que escribir el número varias veces.

El siguiente código resuelve el problema: