Observemos dos cosas que simplificarán el problema:
- Primero, tenga en cuenta que no tiene sentido presionar un botón dos veces; es lo mismo que no presionarlo en absoluto.
- Segundo, el orden de los botones que presionas no hace la diferencia. Si presiona el botón A y luego el botón B, el efecto es esencialmente el mismo que si hubiera presionado el botón B y luego el botón A.
En base a esto, nuestras opciones ahora están considerablemente restringidas: solo necesitamos elegir qué botones presionar y qué botones no.
Decidimos para cada botón, en orden de 1 a n, si presionaremos el botón o no. Para los dos primeros botones, intentemos las 4 posibilidades de voltearlos / no voltearlos.
- ¿Por qué se han desarrollado los algoritmos de ordenamiento O (n ^ 2) (como el ordenamiento por inserción y el ordenamiento por burbuja) y para qué se utilizan?
- ¿Cuáles son algunos libros similares a Programming Pearls?
- ¿Cuál es el mejor algoritmo de eliminación para un árbol de búsqueda binario sin usar un nodo padre adicional?
- ¿Por qué SuperMemo no es tan fácil de usar como Anki?
- ¿Qué haces si la resolución de un problema de algoritmo lleva demasiado tiempo?
Cuando llegue al botón 3, observe que ninguna de sus elecciones futuras afectará en absoluto la lámpara 2. Esto significa que si la lámpara 2 está encendida, no puede voltear el botón 3, porque de lo contrario la lámpara 2 se apagaría permanentemente. Y si la lámpara 2 está apagada, debe elegir presionar 3; de lo contrario, la lámpara 2 nunca se encenderá. De cualquier manera, la decisión de presionar 3 o no es forzada. Por una razón similar, la decisión de presionar 4 o no es forzada porque necesita 3 para tener un estado válido.
Resulta que, después de los dos primeros botones, todas las decisiones posteriores son forzadas . Esto le deja con solo 4 posibilidades de verificación, y el que tiene la menor cantidad de interruptores presionados es el que desea.
