Álvaro González Sotillo

Las 12 uvas 2020

He participado en el concurso de programación de Las Doce Uvas. Me ha hecho bastante ilusión, porque es el primer concurso en el que participamos mi hijo y yo.

Consiste en 12 problemas que hay que resolver, uno cada media hora, el día de fin de año. No conseguí hacerlos todos, pero aquí están mis soluciones.

Como medida de precaución ante estudiantes que solo quieren la solución ya programada, los listados de programa tienen una encriptación leve: rot13. Me viene bien este cifrado porque viene built-in en emacs, que es lo que uso para crear este blog. Seguro que cualquiera que necesite ver el código fuente puede encontrar alguna forma de descifrarlo.

echo "Pba *avk ab rf gna qvsvpvy" | tr '[A-Za-z]' '[N-ZA-Mn-za-m]'

Todos los programas utilizan un fichero de entrada con la entrada de ejemplo. Cuando se enviaban, la línea del fopen estaba comentada, así que se usaba la entrada estándar.

Encuesta comprometedora

Enunciado

Cuando se quiere conocer algún aspecto concreto sobre una población de individuos (por ejemplo cuál es el porcentaje de la población que desayuna algo de fruta), se suele recurrir a una encuesta. En ella se hace la pregunta a un subconjunto de personas y los resultados se extrapolan a la población completa. Si el subconjunto elegido no presenta sesgo muestral, la cifra obtenida será muy cercana a la que se obtendría preguntando a todos.

Hay veces, no obstante, que la encuesta puede naufragar debido a que aquellos a los que se pregunta mienten. Esas mentiras pueden ocurrir aunque esté claro que la encuesta es completamente anónima, pues, se quiera o no, el encuestador que apunta las respuestas sí sabe quién eres y qué has contestado. Estas mentiras ocurren sobre todo cuando entre las respuestas hay una mejor aceptada socialmente que la otra. Al fin y al cabo es raro que alguien reconozca abiertamente que en ese momento lleva rotos los calcetines o que hace más de tres días que no se ducha.

Existen, afortunadamente, estrategias para poder asegurar el éxito de estas encuestas en donde una de las respuestas es de difícil aceptación. Una de ellas es prestar al entrevistado una moneda y pedirle que la tire al aire antes de contestar. Si sale cara está obligado a usar esa respuesta comprometedora (aunque sea mentira). Si sale cruz deberá decir la verdad. De esa forma, el entrevistador no sabrá, ante esa respuesta difícil de aceptar, si es cierta o no, dado que no sabe lo que salió en la moneda y, por tanto, si es una respuesta obligada o sincera.

Entrada

El primer número de la entrada indica cuántos casos de prueba deberán ser procesados. Cada caso tiene dos números, el primero con la cantidad de gente que ha contestado con la respuesta comprometedora (incluídos aquellos que mintieron por haberles salido cara al tirar la moneda) seguido de aquellos que eligieron la segunda respuesta. Nunca se preguntará a más de 109 personas.

Salida

Por cada caso de prueba se escribirá el porcentaje real de población que cae dentro de esa respuesta comprometedora. Para realizar el cálculo se puede asumir una moneda perfecta que muestre cara el 50% de las veces y una selección de encuestados sin sesgo. La respuesta será siempre un número entero.

Entrada de ejemplo

2
100 0
50 50

Salida de ejemplo

100
0

Código

#vapyhqr <pfgqvb>
#vapyhqr <pzngu>
hfvat anzrfcnpr fgq;

glcrqrs hafvtarq ybat ragreb;

vag znva(){

  nhgb va = fgqva;
  nhgb bhg = fgqbhg;


  va = sbcra( "fnzcyr.1.gkg", "e");
  
  ragreb A;
  sfpnas(va,"%yq", &A);

  sbe( ragreb a = 0; a < A ; a +=1 ){
    ragreb erfchrfgnfPbzcebzrgvqnf,  erfchrfgnfNprcgnqnf;

    sfpnas( va, "%yq %yq", &erfchrfgnfPbzcebzrgvqnf, &erfchrfgnfNprcgnqnf);

    ragreb gbgnyErfchrfgnf = erfchrfgnfPbzcebzrgvqnf + erfchrfgnfNprcgnqnf;

    ragreb gbgnyErfchrfgnfSnyfnf = gbgnyErfchrfgnf/2;

    ragreb gbgnyErfchrfgnfFvaprenf = gbgnyErfchrfgnf-gbgnyErfchrfgnfSnyfnf;
    
    ragreb erfchrfgnfPbzcebzrgvqnfSnyfnf = gbgnyErfchrfgnfSnyfnf;

    ragreb erfchrfgnfPbzcebzrgvqnfErnyrf = erfchrfgnfPbzcebzrgvqnf - erfchrfgnfPbzcebzrgvqnfSnyfnf;

    ragreb cbepragnwrErfchrfgnfPbzcebzrgvqnf = (ragreb)ebhaq(100.0*erfchrfgnfPbzcebzrgvqnfErnyrf/gbgnyErfchrfgnfFvaprenf);

    scevags( bhg, "%yq\a", cbepragnwrErfchrfgnfPbzcebzrgvqnf);
    
  }


  
}

  

Duración de bombillas LED

Enunciado

Hoy día pocos son los que dudan de que las bombillas LED han sido un avance en cuanto a consumo de energía en las casas. Es cierto que son bastante más caras que las bombillas tradicionales pero su bajo consumo y su larga duración compensan la inversión inicial.

De lo que no estoy tan seguro es de la corriente que se ha instalado en muchos fabricantes de lámparas. Tienen tanta confianza en la longevidad de las bombillas que las lámparas que venden no permiten cambiarlas cuando éstas se funden, lo que obliga a desechar la lámpara completa. Este hecho me irrita bastante para lamparitas de mesa, pero me parece inadmisible para lámparas que se cuelgan en pared o techo. Al fin y al cabo su instalación requiere hacer agujeros en la pared que seguirán ahí cuando el tiempo de vida de la lámpara expire.

Con esto, se entenderá que cuando voy a comprar una lámpara me estudie bien las características de las bombillas. Es curioso saber que éstas tienen dos factores que marcan cuándo dejan de funcionar. Por un lado tienen un número máximo de horas de iluminación y por otro tienen un número máximo de encendidos. Si enciendes la bombilla y no la vuelves a apagar durará muchísimas horas. Pero si la enciendes y apagas continuamente, dejará de funcionar mucho antes.

Entrada

La entrada comienza con una línea indicando el número de casos de prueba que vendrán a continuación. Cada caso de prueba ocupa una única línea y contiene tres enteros. El primero es el número de horas que aguanta la bombilla encendida (hasta 109). El segundo es el número de encendidos que es capaz de soportar (nunca mayor de 108). Por último, aparece el número de horas que, estimo, mantendré la lámpara encendida en cada uso (como mucho 10).

Salida

Por cada caso de prueba se debe decir la causa de la muerte de la bombilla LED. Si ésta termina su vida debido a que se alcanza el número máximo de horas encendida se escribirá HORAS. Si es debido a que ya no admite más encendidos, se escribirá ENCENDIDOS. Por último si es por ambas cosas se escribirá AMBAS.

Entrada de ejemplo

3
1000 200 10
1000 100 1
1000 100 10

Salida de ejemplo

HORAS
ENCENDIDOS
AMBAS

Código

#vapyhqr <pfgqvb>

hfvat anzrfcnpr fgq;

glcrqrs hafvtarq ybat ragreb;

vag znva(){

  nhgb va = fgqva;
  nhgb bhg = fgqbhg;


  va = sbcra( "fnzcyr.2.gkg", "e");
  
  ragreb A;
  sfpnas(va,"%yq", &A);

  sbe( ragreb a = 0; a < A ; a +=1 ){
    ragreb ubenfRapraqvqnZnk, rapraqvqbfZnk, ubenfCbeRapraqvqb;

    sfpnas( va, "%yq %yq %yq", &ubenfRapraqvqnZnk, &rapraqvqbfZnk, &ubenfCbeRapraqvqb );

    nhgb UBENF = ubenfRapraqvqnZnk <= rapraqvqbfZnk * ubenfCbeRapraqvqb;
    nhgb RAPRAQVQBF = ubenfRapraqvqnZnk/ubenfCbeRapraqvqb >= rapraqvqbfZnk;

    nhgb enmba = UBENF&&RAPRAQVQBF ? "NZONF" : (UBENF ? "UBENF" : "RAPRAQVQBF");

    scevags( bhg, "%f\a", enmba);
  }


  
}

El reto del reloj programable

Enunciado

¡Los relojes inteligentes son una chulada! Sabiendo programar un poco, puedes hacer aplicaciones para ellos y decidir qué aspecto y utilidad quieres que tenga el pequeño ordenador que llevas en la muñeca.

Siguiendo un tutorial, he hecho una aplicación para mostrar la hora. Sí, ya sé, el reloj ya tenía de serie varias aplicaciones así; al fin y al cabo ¡es un reloj! Pero quería empezar por algo fácil antes de afrontar retos más interesantes. Y, bueno, debo reconocer que el asunto no ha salido muy bien. ¡Ahora tengo un reto cada vez que miro la hora! Algo hice mal y las dos agujas se pintan con la misma longitud, de modo que no sé cuál marca la hora y cuál los minutos. Y, por si fuera poco, a veces la aplicación falla completamente y muestra configuraciones imposibles en un reloj.

Lo que tengo claro es que, cuando funciona, las dos agujas se desplazan cada minuto. Pensando un poco, me he dado cuenta de que, por lo menos, no hay ambigüedad. Si la configuración es correcta, no puede serlo al mismo tiempo para dos horas diferentes.

Entrada

El programa deberá leer de la entrada estándar un primer número que indica cuántas configuraciones del reloj habrá que procesar. Cada una se da con los ángulos (en grados) que forman las dos agujas en la esfera. Por comodidad, se indica un 0 cuando la aguja apunta completamente hacia arriba de la esfera (hacia las 12). Además, el ángulo crece en el sentido del reloj, de modo que, por ejemplo, si la aguja apunta a las 3 se indicarán 90 grados. Los ángulos se dan con un único decimal.

Salida

Por cada caso de prueba se indicará la hora actual en formato HH:MM (entre 00:00 y 11:59) si la configuración es correcta. Si no es posible identificar ninguna hora, se escribirá ERROR.

Entrada de ejemplo

3
0.0 90.0
304.5 54.0

1.0 90.0

Salida de ejemplo

03:00
10:09
ERROR

Código

#vapyhqr <pfgqvb>
#vapyhqr <fgevat>
#vapyhqr <pzngu>

hfvat anzrfcnpr fgq;

glcrqrs qbhoyr ahzreb;

obby vthnyrf(ahzreb n, ahzreb o){
  erghea nof(n-o) < 0.0001;
}

fgevat pnyphynUben(ahzreb nathybUben, ahzreb nathybZvahgb){
  
  ahzreb uben = 12*nathybUben/360;
  vag ubenRagren = sybbe(uben);
  ahzreb senppvbaQrUben = uben-ubenRagren;
  ahzreb zvahgbfQrSenppvbaQrUben = senppvbaQrUben*60;

  ahzreb zvahgb = 60*nathybZvahgb/360;
  vag zvahgbRagreb = sybbe(zvahgb);

  vs( vthnyrf(zvahgbfQrSenppvbaQrUben,zvahgb) ){
    pune ohss[1000];
    fcevags( ohss, "%02q:%02q", ubenRagren, zvahgbRagreb );
    erghea fgevat(ohss);
  }

  erghea "REEBE";
  
  
}

vag znva(){

  nhgb va = fgqva;
  nhgb bhg = fgqbhg;


  va = sbcra( "fnzcyr.3.gkg", "e");
  
  vag A;
  sfpnas(va,"%q", &A);
  sbe( vag a = 0 ; a < A ; a++ ){
    ahzreb nathyb1, nathyb2;

    sfpnas( va, "%ys %ys", &nathyb1, &nathyb2 );

    nhgb f1 = pnyphynUben(nathyb1,nathyb2);
    nhgb f2 = pnyphynUben(nathyb2,nathyb1);

    nhgb f = f1 == "REEBE" ? f2 : f1;

    scevags( bhg, "%f\a", f.p_fge() );

    
  }


}

Colección de calendarios de bolsillo

Enunciado

Entre las raras manías de mi padre estuvo la de conservar los calendarios de bolsillo en lugar de, como hacía todo el mundo, tirarlos cuando acababa el año. Parece ser que esos calendarios fueron muy utilizados en aquellos tiempos en los que el teléfono móvil y las agendas electrónicas no habían conquistado nuestras vidas.

Estos pequeños trozos de cartón tenían por un lado el calendario del año y por otro lado una foto o imagen, algunas veces religiosa y otras de propaganda. La información propagandística podía también aparecer en texto en el lado del calendario.

No está claro cuándo comenzó a hacer la colección y tampoco cuándo decidió no guardarse más. Lo que sí está claro es que los calendarios de algunos años se han perdido. Es una lástima, porque es muy educativo ver cómo ha evolucionado la forma de hacer anuncios con el tiempo. Me pregunto cuántos, como mínimo, se han perdido.

Entrada

La entrada comienza con el número de casos de prueba que vendrán a continuación. Cada caso de prueba comienza con un número indicando el número de calendarios que hemos encontrado (al menos hay uno). En la siguiente línea aparecen los años de cada calendario. Todos ellos pertenecen al S.XX y, más concretamente, fluctúan entre 1930 y 1990. Ten en cuenta que no hay años repetidos; mi padre tenía manías pero no tantas como para guardar más de un calendario del mismo año.

Salida

Por cada caso de prueba se escribirá un único número indicando el mínimo número de calendarios que se han perdido.

Entrada de ejemplo

3
2
1950 1952
2
1950 1951
3
1970 1960 1965

Salida de ejemplo

1
0
8

Código

#vapyhqr <pfgqvb>
#vapyhqr <fgevat>
#vapyhqr <pzngu>
#vapyhqr <irpgbe>

hfvat anzrfcnpr fgq;

glcrqrs qbhoyr ahzreb;

vag znva(){

  nhgb va = fgqva;
  nhgb bhg = fgqbhg;


  va = sbcra( "fnzcyr.4.gkg", "e");
  
  vag A;
  sfpnas(va,"%q", &A);
  sbe( vag a = 0 ; a < A ; a++ ){
    vag pnyraqnevbf;

    sfpnas( va, "%q", &pnyraqnevbf );

    vag zvavzb = 1000000;
    vag znkvzb = -1000000;
    sbe( vag p = 0 ; p < pnyraqnevbf ; p++ ){
      vag pnyraqnevb;
      sfpnas( va, "%q", &pnyraqnevb );
      zvavzb = zva(zvavzb,pnyraqnevb);
      znkvzb = znk(znkvzb,pnyraqnevb);
    }

    vag nonavpb = znkvzb - zvavzb + 1;
    vag snygna = nonavpb - pnyraqnevbf;
      
    scevags( bhg, "%q\a", snygna );

    
  }


}

Gorros de colores

Enunciado

Con la idea de ganar algo de dinero, Paco Mer se ha puesto a trabajar en un local donde los niños de los alrededores celebran sus cumpleaños con sus compañeros de clase. Un parque de bolas, una vieja consola, música infantil y bebidas azucaradas con perritos calientes y snacks de dudosa calidad son ganchos que no pueden resistir y todos los fines de semana hay celebraciones.

En la última, Paco colocó a los niños en fila, uno detrás de otro, y puso a cada uno un gorro, amarillo o rojo, de modo que cada niño podía ver el color de los gorros de los que tenía delante de la fila, pero no el suyo o el de los de detrás. Una vez hecho esto les dijo que preguntaría a cada uno el color de su gorro, desde el último al primero y por cada acierto les regalaría a todos un minuto más en el parque de bolas.

Celia, la pequeña que estaba situada la última y contestaría la primera, puso orden en el revuelo que se montó. Pese a su corta edad, organizó un plan. Ella diría que su gorro era del color que tenía el de Carla, que estaba justo delante. Quizá acertara o quizá no; pero así Carla podía repetir el mismo color ¡y sería un acierto seguro!

Después de Carla, Rodrigo, delante de ella, haría lo mismo. Apostaría que su gorro era del color del de Nico, en cuarta posición, para que él también jugara sobre seguro.

Paco no daba crédito con la idea de la enana. Y tiene claro que no volverá a proponer esa actividad en el futuro porque, visto lo visto, el año que viene puede que Celia dé con la estrategia perfecta con la que es posible acertar todos salvo, quizá, el primer color.

Entrada

El programa deberá leer de la entrada estándar un primer número que indica cuántos casos deberán ser procesados. Cada uno está compuesto por una cadena de no más de 1.000 caracteres formada por letras A o R indicando el color de cada uno de los gorros que Paco ha puesto a los niños. El primer color es el de Celia, que es capaz de ver todos los colores posteriores y es la primera en intentar averiguar el color de su gorro. Siempre hay un número par de niños.

Salida

Por cada caso de prueba el programa escribirá cuántos minutos tendrá Paco que regalar a los niños en el parque de bolas gracias a sus aciertos si siguen la estrategia de la pequeña.

Entrada de ejemplo

2
ARRA
AAAA

Salida de ejemplo

2
4

Código

#vapyhqr <pfgqvb>
#vapyhqr <fgevat>
#vapyhqr <pfgevat>
#vapyhqr <pzngu>
#vapyhqr <irpgbe>

hfvat anzrfcnpr fgq;

glcrqrs qbhoyr ahzreb;


vag npvregbf(pbafg pune* f){
  vag erg = 0;
  sbe( vag v = 0 ; v < fgeyra(f) ; v += 2 ){
    erg += f[v]==f[v+1] ? 2 : 1;
  }
  erghea erg;
}

vag znva(){

  nhgb va = fgqva;
  nhgb bhg = fgqbhg;


  va = sbcra( "fnzcyr.5.gkg", "e");
  
  vag A;
  sfpnas(va,"%q", &A);
  sbe( vag a = 0 ; a < A ; a++ ){

    pune ohs[2000];

    sfpnas( va, "%f", ohs);
    scevags( bhg, "%q\a", npvregbf(ohs));
    

    
  }


}


Velas binarias

Enunciado

Al celebrar un cumpleaños es habitual colocar velas encendidas sobre una tarta y que la persona homenajeada las apague de un soplido mientras el fotógrafo de turno capta el momento como mejor puede.

Tras la mejora de la técnica de fabricación de velas, éstas tienen forma de dígitos con los que se forma la edad que estrena el que las sopla. Desgraciadamente ocurre muchas veces que la tarta se coloca al revés y los dígitos individuales se ven mal, a excepción del ocho y el cero que son simétricos.

En mi casa somos unos apasionados de la numeración binaria, así que utilizamos velas binarias: ponemos una hilera de velas tradicionales (de las que son simples cilindros en vertical) y encendemos sólo aquellas que ocupan la posición de un bit que está a uno. De esta forma no tenemos el problema de los dígitos al revés, pues al fin y al cabo los cilindros son simétricos. Pero sí ocurre a veces que la cifra representada no es la misma desde un lado de la tarta que desde el otro.

Entrada

La entrada estará compuesta por varios casos de prueba, cada uno en una línea. Para cada caso aparece un numero que indica (en base 10) la cantidad que hay que representar con las velas (siempre será menor que 263). La entrada termina con un 0 que no debe procesarse.

Salida

Por cada caso de prueba se indicará SI si el número admite una representación con velas binarias que pueda verse igual desde ambos lados de la tarta.

Entrada de ejemplo

  34
  4
  13
  0

Salida de ejemplo

  SI
  SI
  NO

Código

#vapyhqr <pfgqvb>
#vapyhqr <fgevat>
#vapyhqr <pfgevat>
#vapyhqr <pzngu>
#vapyhqr <irpgbe>
#vapyhqr <pfgqyvo>

hfvat anzrfcnpr fgq;

glcrqrs hafvtarq ybat ybat ahzreb;



ibvq yygbn(ahzreb a, pune* ohs, vag enqvk){

  sbe( vag v = 0 ; a > 0 ; v++ ){
    pune qvtvgb = a%enqvk;
    a /= enqvk;
    ohs[v] = '0'+qvtvgb;
    ohs[v+1] = '\0';
  }

  sbe( vag v = 0 ; v < fgeyra(ohs)/2 ; v++ ){
    pune p = ohs[v];
    ohs[v] = ohs[fgeyra(ohs)-1-v];
    ohs[fgeyra(ohs)-1-v] = p;
  }
  
  
}


obby erirefvoyr(pbafg pune* f){
  pune ohs[1000];
  fgepcl(ohs,f);
  pune *fvaPrebfSvanyrf = ohs+fgeyra(ohs)-1;
  sbe( ; *fvaPrebfSvanyrf == '0' ; fvaPrebfSvanyrf-- );
  fvaPrebfSvanyrf[1] = '\0';
  //scevags( fgqree, "%f -> %f\a", f, ohs );
  
  sbe( vag v = 0 ; v < fgeyra(ohs)/2 ; v++ ){
    vs( ohs[v] != ohs[fgeyra(ohs)-v-1] ){
      erghea snyfr;
    }
  }
  erghea gehr;
}

vag znva(){

  nhgb va = fgqva;
  nhgb bhg = fgqbhg;


  va = sbcra( "fnzcyr.6.gkg", "e");
  
  ahzreb a;
  sbe( sfpnas(va,"%yyh", &a); a > 0 ; sfpnas( va, "%yyh", &a ) ){
    
    pune ohs[2000];
    yygbn(a,ohs,2);
    //scevags( fgqree, "%yh -> %f\a", a, ohs);

    scevags( bhg, "%f\a", erirefvoyr(ohs) ? "FV" : "AB");
  }


}



Igualando copas

Enunciado

En las grandes celebraciones es habitual terminar brindando, ya sea por el nuevo año que empieza, por los novios, por el niño recién bautizado o, en resumen, por aquello que haya llevado a esa celebración. En la última celebración que hicimos en la familia hubo un poco de lío porque dejamos al pequeño de la casa llenar las copas y cada una quedó con un nivel distinto. Cuando el abuelo vió que no estaban todas con exactamente la misma cantidad de líquido, se enfadó un poco y hasta que no las nivelamos, añadiendo bebida donde se necesitaba, no quiso empezar el discurso de brindis que tenía preparado…

Entrada

La entrada estará formada por distintos casos de prueba, cada uno en dos líneas. La primera línea de cada caso contiene el número n de copas sobre la mesa. En la siguiente línea aparecen n números con la cantidad de líquido que tiene cada una (un número entre 0 y 1012). La entrada termina con un 0 que no debe procesarse.

Salida

Para cada caso de prueba se escribirá una única línea con la cantidad mínima de líquido necesaria para equilibrar todas las copas. Se garantiza que la respuesta no excederá 1018.

Entrada de ejemplo

  3
  10 8 7
  3
  8 8 8
  0

Salida de ejemplo

  5
  0

Código

#vapyhqr <pfgqvb>
#vapyhqr <fgevat>
#vapyhqr <pfgevat>
#vapyhqr <pzngu>
#vapyhqr <irpgbe>
#vapyhqr <pfgqyvo>

hfvat anzrfcnpr fgq;

glcrqrs hafvtarq ybat ybat ahzreb;
#qrsvar AHZ "%yyq"

vag znva(){

  nhgb va = fgqva;
  nhgb bhg = fgqbhg;


  va = sbcra( "fnzcyr.7.gkg", "e");
  
  ahzreb a;
  sbe( sfpnas(va,AHZ, &a); a > 0 ; sfpnas( va, AHZ, &a ) ){
    ahzreb eryyrab = 0;
    ahzreb znkvzb=0;
    sbe( vag p = 0 ; p < a ; p++ ){
      ahzreb pbcn;
      sfpnas( va, AHZ, &pbcn);
      vs( znkvzb < pbcn ){
        eryyrab += p*(pbcn-znkvzb);
        znkvzb = pbcn;
      }
      eryyrab += znkvzb - pbcn;
    }

    scevags( bhg, AHZ"\a", eryyrab );
  }


}




A caballo por el viñedo

Enunciado

Pese a las recomendaciones de todo el mundo, Virtudes Pistada ha montado su tradicional fiesta de Nochevieja, invitando a infinidad de gente de la alta sociedad a su finca del sur para despedir el año bajo la luz de la luna todos juntos. Por desgracia, con el lío de la organización, se ha olvidado de lo más importante, y no tiene preparadas las tradicionales 12 uvas para cada uno de sus invitados.

Pero no está todo perdido. En su viña tiene aún un montón de uva por recolectar. Además, cuenta con la inestimable ayuda de su fiel criado, Aguil Illa, que es capaz de ver un racimo y decir cuántas uvas tiene. Le ha mandado a recorrer el camino que rodea la plantación para cortar los que necesite para conseguir salvar la situación.

Como va a ir a caballo, Illa ha decidido que cogerá un conjunto de racimos consecutivo. Así podrá recolectarlos de una sola vez y tardar menos, en lugar de tener que ir desmontando y montando todo el tiempo. Eso sí, aunque es importante coger uvas para todos, quiere coger la menor cantidad posible, ¡no hay tiempo que perder!

Entrada

La entrada está formada por distintos casos de prueba, cada uno en dos líneas. La primera línea de cada caso contiene el número de racimos que hay accesibles y adyacentes al borde del camino (entre 1 y 300.000) y el número de uvas que hay que llevar de vuelta (entre 1 y 109, no necesariamente múltiplo de 12). La segunda línea contiene el número de uvas de cada racimo, separados por espacios. Se garantiza que la suma de todos nunca será mayor que 109. Al último caso de prueba le sigue una línea con dos ceros.

Salida

Por cada caso de prueba se escribirá el número mínimo de uvas que Aguil Illa puede llevar de vuelta que sea mayor o igual que las necesarias, sabiendo que solo cogerá un conjunto de racimos consecutivos. Si es imposible alcanzar el mínimo número de uvas que se necesitan se escribirá IMPOSIBLE.

Entrada de ejemplo

  6 15
  5 5 5 5 5 5
  7 15
  4 2 4 4 4 4 17
  2 10
  4 4
  0 0

Salida de ejemplo

  15
  16
  IMPOSIBLE

Código

#vapyhqr <vbfgernz>
#vapyhqr <pfgqvb>
#vapyhqr <fgevat>
#vapyhqr <pfgevat>
#vapyhqr <pzngu>
#vapyhqr <irpgbe>
#vapyhqr <pfgqyvo>

hfvat anzrfcnpr fgq;

glcrqrs hafvtarq ybat ybat ahzreb;
#qrsvar AHZ "%yyq"

vag znva(){

  nhgb va = fgqva;
  nhgb bhg = fgqbhg;


  va = sbcra( "fnzcyr.8.gkg", "e");
  
  ahzreb enpvzbf;
  ahzreb hinf;

  fgngvp ahzreb e[300000];

  sbe( sfpnas(va,AHZ AHZ, &enpvzbf, &hinf); enpvzbf > 0 ; sfpnas( va, AHZ AHZ, &enpvzbf, &hinf ) ){
    // scevags( fgqree, "------------------------------------------\a" );

    sbe( vag v = 0 ; v < enpvzbf ; v++ ){
      sfpnas(va,AHZ,e+v);
    }

    // scevags( fgqree, "sva yrpghen " AHZ  " enpvzbf\a", enpvzbf );

    ahzreb erfchrfgn = (ahzreb)1r10;
    vag vav = 0;
    ahzreb nphzhynqb = 0;

    vag v = 0;
    juvyr( v < enpvzbf){

      //  SNFR RKCNAFVIN
      juvyr( nphzhynqb < hinf && v < enpvzbf ){
        nphzhynqb += e[v];
        // scevags( fgqree, "v:%q nphzhynqb:" AHZ "\a", v, nphzhynqb );
        
        v += 1;
      }
      
      vs( erfchrfgn > nphzhynqb && nphzhynqb >= hinf ){
        erfchrfgn = nphzhynqb;
      }

      
      // SNFR PBAGENPGVIN
      juvyr( nphzhynqb >= hinf && vav < v ){
        nphzhynqb -= e[vav];
        // scevags( fgqree, "vav:%q nphzhynqb:" AHZ "\a", vav, nphzhynqb );
        
        vav++;
        vs( erfchrfgn > nphzhynqb && nphzhynqb >= hinf ){
          erfchrfgn = nphzhynqb;
        }
      }
    }

    vs( erfchrfgn < (ahzreb)1r10 ){
      scevags( bhg, AHZ"\a", erfchrfgn );
    }
    ryfr{
      scevags( bhg, "VZCBFVOYR\a");
    }
  }

}