La barda de la calle
- O(n²) · Muy difícil
- Plan completo
- Python
- JavaScript
- comparaciones
- ciclos
- listas
Enunciado
Los vecinos de la cerrada se repartieron la barda larga para pintarla el sábado, y cada uno apuntó en una libreta de qué tabla a qué tabla le tocó. Nadie miró los tramos de los demás. Óscar, el pintor que revisa la obra, sabe que donde caen dos manos o más la pintura se cuartea, y quiere saber cuántas tablas va a tener que lijar.
Recibes largo (entero de 0 en adelante; las tablas van de la 0 a la largo - 1) y desde y hasta, dos listas de enteros del mismo tamaño que pueden venir vacías: el vecino i pintó de la tabla desde[i] a la hasta[i], las dos incluidas, con 0 <= desde[i] <= hasta[i] < largo. Regresa, como entero, cuántas tablas recibieron pintura de 2 vecinos o más; una tabla con tres manos o más cuenta una sola vez.
Con largo 10, desde [0, 3, 5] y hasta [4, 6, 5]: el vecino 0 pinta de la 0 a la 4, el 1 de la 3 a la 6 y el 2 solo la 5. Las tablas 3 y 4 las pintan los vecinos 0 y 1, y la 5 los vecinos 1 y 2: regresas 3.
Sin vecinos, o si ningún tramo se encima con otro, regresas 0.
Ejemplos
El ejemplo
10, [0, 3, 5], [4, 6, 5] → 3
Tramos que solo se tocan
8, [0, 3, 6], [2, 5, 7] → 0
Un solo vecino
5, [1], [3] → 0
Tres manos cuentan una vez
6, [0, 1, 2], [5, 4, 3] → 4
Los dos extremos de la barda
7, [0, 6, 0], [3, 6, 6] → 5
Además de estas, el reto tiene pruebas ocultas que se revelan al enviar tu solución.
Empiezas con esto
Python
def a_lijar(largo, desde, hasta):
passJavaScript
function aLijar(largo, desde, hasta) {
}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.