Skip to content

Solución: anuncios en el paseo marítimo

by en 27/05/2014

Hola!

Llega el momento de dar la solución a nuestro último acertijo. En él, os hablábamos de una población costera que ha colocado vallas publicitarias a lo largo del paseo marítimo, y de una empresa que quiere conseguir que los viandantes vean su anuncio al menos un número de veces en sus paseos. Para eso, conoce los puntos de inicio y de fin de los recorridos que realizan, y necesita averiguar el mínimo número de vallas que debe alquilar para conseguir su objetivo.

Gualterio nos dio su solución y… ¡acertó! Aunque haya sido en el tiempo de descuento por nuestro retraso en la publicación de la solución 🙂 su contribución es igual de válida de modo que ¡enhorabuena, un acertijo más! 🙂

Pero basta de preámbulos y vamos con la explicación. La primera situación por la que os preguntábamos era fácil. En ella, la empresa quiere que los turistas vean su anuncio al menos 5 veces, y hay sólo dos recorridos a cubrir:

  • Del número 1 al número 10 o, abreviando, (1, 10).
  • Del número 30 al 20: (30,20)

En este caso la respuesta es muy sencilla, dado que los dos recorridos no se solapan. Las vallas que la empresa alquile para que los turistas que hacen el camino (1,10) vean su anuncio no serán vistas por los turistas que hagan el recorrido (30, 20). Por tanto, será necesario alquilar 5 vallas para cada uno, por lo que el mínimo será de 10.

La siguiente pregunta es un poco más complicada. Consistía también en conseguir que los turistas vieran 5 vallas publicitarias, pero ahora los recorridos son (17-21), (10-20), (25-5), donde sí hay solapamiento.

17-21
10-20
25-5

Con la imagen delante, no resulta ya tan complicado. Lo que queremos es minimizar el número de vallas que alquilamos, de modo que queremos coger aquellas que más turistas vean. Claramente en este caso tenemos que coger las cinco vallas del rango 17-21. Las 5 serán vistas por los turistas del último recorrido, (25, 5) de modo que para ellos no hay que alquilar más. Tan sólo nos falta una más para el rango 10-20. Podemos coger la que queramos (por ejemplo la situada en el número 16):

17-21
10-20
25-5
Alq.

Alquilando las vallas marcadas en la última fila, se puede comprobar que todos los turistas ven al menos 5 veces nuestro anuncio.

¿Cómo podemos hacer el cálculo de una manera sistemática? Si el número de recorridos crece, cada vez resultará más complicado utilizar la intuición para colocar las vallas, incluso aunque nos hagamos el dibujo. De hecho, la última pregunta es bastante más larga: 6 vallas y recorridos (7, 10), (25, 33), (32, 62), (50, 20), (44, 9), (50, 86) y (24, 19).

Para resolverlo, lo que hacemos es utilizar un algoritmo voraz diseñado para la ocasión, tal y como ya hicimos en otros acertijos anteriores. Lo que haremos será ir alquilando vallas para conseguir que cada recorrido de un turista tenga nuestros 6 anuncios, de tal manera que garanticemos que, al final, el número de vallas alquiladas sea el mínimo necesario.

¿Y cómo lo conseguimos? La idea principal es ordenar los recorridos por punto de finalización. Da igual lo largo o cortos que sean. Lo importante es dónde acaban. Ten en cuenta que como el orden es importante, usaremos siempre el sentido “de menor a mayor” en los recorridos de manera que, por ejemplo, al recorrido (50, 20) le daremos la vuelta para simular que todos los turistas van en sentido ascendente de la numeración. Esto no es importante para el resultado final, pero sí para que nuestro mecanismo de obtención de la respuesta funcione.

Con esta idea, los recorridos que tenemos que cubrir (ordenados ya de menor a mayor por punto de finalización) son (7, 10), (19, 24), (25, 33), (9, 44), (20, 50), (32, 62), (50, 86). Fijate que, por ejemplo, el recorrido (9, 44) empieza antes que el (25,33). Pero lo analizaremos después porque acaba más tarde.

Ahora empezamos a analizar cada recorrido con el primero, (7, 10). Tenemos que conseguir que los turistas vean 6 vallas, y sin embargo estos turistas sólo recorren 4. Tendremos que alquilarlas todas y conformarnos con eso. Para los turistas (19, 24) nos toca hacer lo mismo: alquilar las 6 vallas de su recorrido.

El acertijo se pone más interesante con el siguiente, (25, 33). Tenemos que alquilar 6 vallas; pero, ¿cuales? Dado que tenemos ordenados los recorridos por finalización nos interesa comprar las vallas del final para que así los siguientes recorridos, que siempre acaban más tarde, tengan posibilidad de ver también las vallas que alquilamos ahora. Es decir, sin saber de antemano qué vendrá después, es mejor alquilar las vallas (28, 33), en lugar de alquilar (25, 30), porque todos los recorridos que vendrán después terminan pasado el número 33, y por tanto hay más probabilidades que vean la valla en la posición 28 que la valla en la posición 25 (dependiendo de dónde empiecen).

Tras haber analizado los tres primeros recorridos, por tanto, hemos alquilado las vallas (7, 10), (19, 24) y (28, 33). El siguiente recorrido que procesamos es (9, 44) pero este recorrido ya tiene dentro más de 6 de nuestros anuncios gracias a las vallas alquiladas antes, por lo que no añadimos ninguna más. Con (20, 50) ocurre igual.

Con el penúltimo recorrido, (32, 62), ocurre algo intermedio. En él son visibles dos vallas ya alquiladas, la 32 y la 33. Quedan 4 más por alquilar. Pero… ¿cuales? Como hemos dicho antes, lo más conservador es alquilarlas al final, en el rango (59, 62). De esa manera los recorridos que vengan después (y que acaban más tarde) podrían aprovecharse de ellas. Y… ¡así es! El último recorrido, (50, 86) ve esas 4 vallas también. Si hubiéramos alquilado vallas por detrás del 50 no las habríamos reutilizado.

Sólo falta alquilar dos vallas más para el último recorrido (en 85 y 86) y habremos terminado. Al final hemos alquilado (7, 10), (19, 24), (28, 33), (59, 62) y (85, 86), que hacen un total de 22 vallas. Podemos conseguir que los turistas vean nuestras 6 vallas alquilando otras, pero nunca podremos conseguirlo con menos de 22 vallas 🙂

Ahora que os hemos contado el truco del acertijo, quizá queráis intentar programarlo. Si lo hacéis y queréis probar vuestra solución, podéis hacerlo aquí.

¡Hasta el próximo!

Anuncios

From → Soluciones

Dejar un comentario

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: