Aprende Python con competiciones de programación. #1. Code Jam 2016. Counting Sheep
Problema
Bleatrix Trotter la oveja ha ideado una estrategia que le ayuda a dormirse más rápido. Primero, escoge un número N. Luego empieza a nombrar N, 2 × N, 3 × N, y así sucesivamente. Cada vez que nombra un número, piensa en todos los dígitos de ese número. Lleva un registro de los dígitos (0, 1, 2, 3, 4, 5, 6, 7, 8, y 9) que ha visto al menos una vez hasta ahora como parte de cualquier número que haya nombrado. Una vez que haya visto cada uno de los diez dígitos por lo menos una vez, se dormirá.
Bleatrix debe comenzar con N y siempre debe nombrar (i + 1) × N directamente después de i × N. Por ejemplo, supongamos que Bleatrix elige N = 1692. Ella contaría como sigue:
N = 1692. Ahora ha visto los dígitos 1, 2, 6 y 9.
2N = 3384. Ahora ha visto los dígitos 1, 2, 3, 4, 6, 8, y 9.
3N = 5076. Ahora ha visto los diez dígitos y se duerme.
¿Cuál es el último número que nombrará antes de quedarse dormida? Si cuenta para siempre, escriba INSOMNIA en su lugar.
Entrada
La primera línea de la entrada da el número de casos de prueba, los casos de prueba de T. Cada test T consiste en una línea con un solo número entero N, el número que Bleatrix ha elegido.
Salida
Para cada caso de prueba, envíe una línea que contenga Case#x: y, donde x es el número del caso de prueba (empezando por 1) y “y” es el último número que Bleatrix nombrará antes de quedarse dormida, de acuerdo con las reglas descritas anteriormente.
Límites
1 ≤ T ≤ 100.
Conjunto de datos pequeño (small dataset)
0 ≤ N ≤ 200.
Conjunto de datos grande (large dataset)
0 ≤ N ≤ 106.
Muestra
En el Caso #1, ya que 2 × 0 = 0, 3 × 0 = 0, y así sucesivamente, Bleatrix nunca verá ningún otro dígito que no sea 0, por lo que contará para siempre y nunca se dormirá. ¡Pobre oveja!
En el Caso #2, Bleatrix nombrará 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. El 0 será el último dígito necesario, por lo que se dormirá después de las 10.
En el Caso #3, Bleatrix nombrará 2, 4, 6… y así sucesivamente. No verá el dígito 9 en ningún número hasta el 90, momento en el cual se dormirá. Para entonces, ya habrá visto los dígitos 0, 1, 2, 3, 4, 5, 6, 7 y 8, que aparecerán por primera vez en los números 10, 10, 2, 30, 4, 50, 6, 70 y 8, respectivamente.
En el Caso #4, Bleatrix nombrará 11, 22, 33, 44, 55, 66, 77, 88, 99, 110 y luego se dormirá.
El Caso #5 es el que se describe en la declaración del problema. Tenga en cuenta que sólo aparecería en el conjunto de datos Grande, y no en el conjunto de datos Pequeño.
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Vamos a analizar una de las soluciones propuestas por uno de los mejores programadores de competición en Python, finalista de la codejam 2016, Nore.
— — — — — — — — — — — — — — The End — — — — — — — — — — — — —
Si te gusta esta pequeña y gratuita revista puedes ayudar simplemente compartiéndola o suscribiéndote a la revista. Soy Rubén Ruiz, trabajo en la industria financiera en Inteligencia Artificial. Como proyecto personal llevo esta pequeña revista donde experimentamos con Inteligencia Artificial…
Puedes también seguirme en:
Instagram (Vida personal, es divertido) => @rubenruiz_t
Youtube (Canal sobre IA, intento que sea divertido )=> Rubén Ruiz A.I
Github (Donde subo mi código, esto ya no es tan divertido) => RubenRuizT
