Resolviendo el #TuentiContest: Problema 9 – Christmas lights

Pasado los festejos con los ganadores del evento, sigo publicando mis soluciones. Y con esta llego al Ecuador de mi participación. En el problema 9 nos ponemos navideños. Ahora nos dan una extensión de luces de navidad y nos preguntan, pasado cierto tiempo, cuáles bombillas están encendidas. Al igual que en el problema anterior la solución es en C++. Personalmente debo decir que este problema me gustó. Es verdad que es bastante sencillo de resolver y no requiere mayor tratamiento pero, a diferencia de los dos anteriores, esta solución no está escrita en ningún libro por lo que hace falta una reflexión más allá de “Este sale en el Cormen y es el algoritmo de Fulano” (o quizás deba decir ahora Wikipedia). Análisis del problema Es momento de descansar de programaciones dinámicas y recursiones. A pesar de que el planteamiento del problema es un poco complicado por cómo está escrito (y es que si lo explican de forma más sencilla, nos resuelven el problema), es fácil ver que en los instante de tiempo impares, las luces pares se encienden y al revés. La otra condición es que las luces van participando en el proceso a medida que pasa el tiempo, es decir, en el primer segundo solo la primera participa, luego las primeras dos, etc. Asumo que si son n luces, desde el instante n en adelante, todas las luces participan por lo que solo interesa saber la paridad del instante. Entre las soluciones publicadas de los otros participantes, me he encontrado con una interpretación distinta, en la que el instante n+1 es un reinicio del juego de luces, con lo cual es equivalente al instante cero. No sé qué opinas al respecto. Entiendo la variante pero no la veo planteada en el problema. Entonces, con las dos consideraciones iniciales nuestro algoritmo simplemente verá si el instante que nos preguntan es par o impar (para saber cuáles encender) y revisará cuáles luces encender en función del tiempo que haya pasado. Solución enviada Como te comenté antes, este código es para descansar. Una lectura de variables simple, un if para el mensaje de texto especial en caso de que no hayan luces y una iteración para encenderlas si hace falta.

#include <iostream>
using namespace std;

int main() {
  int cases;
  cin >> cases;
  while(cases-- > 0){
    int lamp;
    int time;
    cin >> lamp >> time;
    int max = min(time,lamp);
    if(lamp == 1 && time % 2 == 0){
      cout << "All lights are off : (" << endl;
    } else {
      int i = 1-(time%2);
      for(;i<max;i+=2){
        cout << i;
        if(i+2<max) cout << " ";
      }
      cout << endl;
    }
  }
  return 0;
}

Bajo mi interpretación de que las luces nunca se reinician, la única manera en que estén todas apagadas es si solo hay una bombilla y es un instante de tiempo par. La carita se ve más lánguida de lo exigido por el plugin de WordPress que me la cambiaba por :( si la dejaba tal cual. Curioso. Solución mejorada Aquí no veo pa’ dónde agarrar. Si me sobran líneas es por exceso de legibilidad. Les ofrezco una versión un poco más ofuscada en Perl para tratar de hacerlo en muy pocas líneas.

foreach (1 .. <>) {
  $l = <>; $t = <>; $max = ($t < $l) ? $t : $l; $o="";
  for($i=1-($t % 2); $i<$max; $i+=2) { $o .= "$i ";}
  print "$on" if length $o>0 or print "All lights are off : (";
}

Aquí me permito que la salida tenga un espacio en blanco al final. Un trim me haría más estricto pero si a ellos le permitimos entradas raras antes, que nos dejen esta 😉 Y tú, ¿cómo lo resolviste?

2 thoughts on “Resolviendo el #TuentiContest: Problema 9 – Christmas lights

Deja un comentario