Luciérnaga
Una luciérnaga japonesa ha volado dentro de una cueva llena de obstáculos: estalagmitas (subiendo del suelo) y estalactitas (colgando del techo). La cueva es de unidades de largo (donde
es par) y
unidades de alto. El primer obstáculo es una estalagmita después las estalactitas y estalagmitas siguen de manera alterna.
Aquí tienes un ejemplo de una cueva de unidades de largo y
unidades de alto (la imagen corresponde al segundo ejemplo de entrada):
La luciérnaga japonesa no es del tipo que volaría alrededor del obstáculo, en cambio escoge una altura única y atacar de un extremo de la cueva al otro destruyendo todos los obstáculos en su camino con sus poderosos movimientos de kung-fu. En el ejemplo anterior, escogiendo el 4to nivel desde la tierra la luciérnaga destruye ocho obstáculos:
Esta no es la mejor opción porque la luciérnaga terminará menos cansada si escoge cualquiera de los niveles uno o cinco, destruyendo sólo siete obstáculos. A usted se le dará la altura y longitud de la cueva y los tamaños de todos los obstáculos.
Escriba un programa que determine el número mínimo de obstáculos que la luciérnaga necesita destruir para alcanzar el final de la cueva, y en cuántos niveles distintos puede lograr ese número.
Entrada
La primera línea de la entrada contiene dos enteros y
,
,
, el largo y alto de la cueva.
siempre será par. Las próximas
líneas contienen el tamaño de los obstáculos, uno por cada línea, el primer obstáculo es una estalagmita después las estalactitas y estalagmitas se presentan de manera alterna. Todos los tamaños son enteros positivos menores o iguales que
.
Salida
La salida debe contener en una sola línea dos enteros separados por un simple espacio. El primer número es el mínimo de obstáculos que la luciérnaga debe destruir y el segundo número es la cantidad de niveles en la que puede alcanzarlo.
Ejemplo de Entrada 1
6 7
1
5
3
3
5
1Ejemplo de Salida 1
2 3Ejemplo de Entrada 2
14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3Ejemplo de Salida 2
7 2
Comments
Gracias, voy a ver
Cómo puedo optimizar la solución a este problema?
Se añadió una editorial.