Esto se puede resolver mediante el uso de programación dinámica. Aquí está el algoritmo:
1. Para N <7, la salida es N misma.
2. Para producir el número máximo de A, la secuencia de N pulsaciones de teclas que se utilizarán terminará con un sufijo de Ctrl-A, Ctrl-C, seguido de solo Ctrl-V (para N> 6).
3. La tarea es encontrar el punto crítico después del cual obtenemos el sufijo anterior de las pulsaciones de teclas.
4. Un punto crítico es esa instancia después de la cual solo debemos presionar Ctrl-A, Ctrl-C una vez y las únicas Ctrl-V después para generar el número máximo de A.
5. Realizamos un bucle de N-3 a 1 y elegimos cada uno de estos valores para el punto crítico, y calculamos esa cadena óptima que producirían. Al calcular el número óptimo de As para cada punto crítico, utilizamos el número óptimo de As ya calculado para el número de pulsaciones de teclas <N.
6. Una vez que finalice el bucle anterior, tendremos el máximo de las longitudes óptimas para varios puntos críticos, dándonos así la longitud óptima para N pulsaciones de teclas.
Fuente: para imprimir el número máximo de As utilizando las cuatro teclas dadas.
Puede ver este video para obtener una explicación detallada de la solución con prueba de corrección.
- ¿De qué se trata exactamente la conjetura P / NP? ¿Por qué es tan importante demostrarlo?
- Cómo comprender completamente los condicionales en matemáticas discretas
- ¿Qué criterios utiliza para determinar si un artículo / publicación es útil para usted?
- ¿Cómo podemos abordar para resolver el problema de 'Infinite House of Pancakes' de Google Code Jam 2015?
- ¿Por qué si tenemos una reducción en el tiempo polinomial de un problema de P a un problema de NP, esto no muestra que P = NP (pero al contrario)?
