Las pistas del cumpleaños
- O(n²) · Muy difícil
- Plan completo
- Python
- JavaScript
- ciclos
- listas
- índices
Enunciado
Para los ocho años de Emiliano, su tía llenó el patio de cajas de zapatos numeradas desde 0, y adentro de cada una dejó una nota con el número de la caja que toca abrir después. Emiliano abre primero la caja 0, lee la nota, va a la caja que dice, y así sigue. El juego se acaba cuando una nota lo manda a una caja que ya abrió: esa no cuenta otra vez.
Recibes siguiente, una lista con al menos un entero: siguiente[i] es el número que trae la nota de la caja i, siempre entre 0 y el largo menos 1, y puede ser la misma caja. Varias notas pueden mandar a la misma caja, y puede haber cajas que nunca se abren.
Regresa, como entero, cuántas cajas distintas abrió Emiliano.
Con [2, 0, 3, 1] abre la 0, que lo manda a la 2; la 2 lo manda a la 3, la 3 a la 1 y la 1 de vuelta a la 0, que ya abrió: regresas 4.
Con [1, 1, 0] abre la 0 y la 1, y la 1 lo manda a sí misma: regresas 2.
Ejemplos
El ejemplo
[2, 0, 3, 1] → 4
Una nota que apunta a su caja
[1, 1, 0] → 2
Una sola caja
[0] → 1
Dos cajas se quedan cerradas
[1, 0, 3, 2] → 2
Vuelve a una caja de en medio
[1, 2, 3, 1, 0, 4] → 4
Además de estas, el reto tiene pruebas ocultas que se revelan al enviar tu solución.
Empiezas con esto
Python
def cajas_abiertas(siguiente):
passJavaScript
function cajasAbiertas(siguiente) {
}Se abre en el navegador, con el editor y las pruebas. Este reto es del plan completo; los de O(1) y O(log n) son gratis.
Más retos de O(n²)
- Lluvia entre las rocaslistas · ciclos · comparaciones
- Los avisperos del viverorejillas · textos · ciclos
- Los caballos del kancomparaciones · ciclos · listas
- Los caminos por la obrarecursión · rejillas · diccionarios
- Los camiones que pasaronlistas · comparaciones · condicionales
- Los charcos del patiorejillas · recursión · ciclos