Copiado al portapapeles
Descripción
En un juego donde participan dos jugadores, un numero par de cartas están formadas en una fila.
En cada carta en la parte de arriba existe un entero positivo. Los jugadores toman turnos removiendo una carta por cualquiera de los dos extremos finales de la fila y los van acomodando en una pila. El jugador con la suma de cartas mas alta gana el juego.
Ahora una estrategia es tomar la carta con mayor numero en alguno de los dos extremos, esta estrategia se llama greedy. Sin embargo esto no siempre es lo mas optimo, en el siguiente ejemplo: (El primer jugador gana, si el primero toma la carta con el numero 3 en lugar de tomar la con el numero 4)
3 2 10 4
Tu tienes que determinar exactamente cuan mala es la estrategia greedy que usara el segundo jugador pero el primer jugador es libre de usar cualquier estrategia.
Entrada
Van a existir múltiples casos de prueba. Cada test va contener una linea. Cada linea va contener un entero par $n$ seguido por $n$ números enteros positivos. Un valor $n = 0$ indica el final de los casos.
Tu puedes asumir que $n$ es no mas de $1000$. Ademas tu puedes asumir que la suma de los numero en las cartas no excede $1000000$.
Salida
Por cada caso de prueba tu debes imprimir una linea de la siguiente manera:
“En el juego $m$, la estrategia greedy pierde por $p$ puntos.” (sin comillas).
Donde $m$ es el numero del juego (empezando por $1$) y $p$ es la máxima posible diferencia entre el puntaje del primer jugador y el segundo jugador cuando el segundo usa la estrategia greedy.
Cuando se usa la estrategia greedy se toma el mayor numero de alguno de los extremos. Si los dos numero de los extremos son iguales se toma el del final izquierda.