Los premios de las tragaperras
Las máquinas tragaperras fueron las primeras máquinas de apuestas automáticas. El jugador introduce en ellas una determinada cantidad de dinero, que apuesta esperando conseguir alguna combinación ganadora en los rodillos. La máquina proporciona un pequeño tiempo de juego y, eventualmente, un premio en efectivo.
Aunque hoy en día la mayoría son digitales, la primera máquina tragaperras, de finales del siglo XIX, era completamente mecánica; de hecho el número de combinaciones que era capaz de identificar en sus tres rodillos era muy pequeño debido a la dificultad de fabricación, por lo que los premios que proporcionaba estaban limitados.
Tras el rotundo éxito del invento, las legislaciones de los diferentes países que las admitieron se afanaron por regular la cantidad de premios que las máquinas debían proporcionar. Desde entonces, se fuerza así a una cantidad mínima de reembolsos; el secreto mejor guardado es, naturalmente, cuándo los darán. A veces, ni siquiera el fabricante lo sabe; son las llamadas máquinas de azar en las que el porcentaje de pagos se consigue estadísticamente. Sin embargo, algunos modelos mecánicos antiguos generaban los premios cíclicamente. Esos ciclos se guardaban celosamente: un jugador que conociera el ciclo de una máquina sabría cuál era el mejor momento para empezar a echar monedas, y cuándo parar.
Entrada
La entrada está compuesta por múltiples casos de prueba. Cada uno comienza con la longitud del ciclo, 1 ≤ L ≤ 1.000.000, seguido de su descripción en otra línea.
El ciclo está compuesto por una secuencia de L números, indicando el beneficio neto del jugador en cada partida. Así, un valor de −1 indica que el jugador echa una moneda y la pierde, al no conseguir premio. Un valor 1 ≤ P < 100.000 indica que el jugador echa una moneda y a cambio la máquina le premia con P + 1 monedas (consigue un beneficio neto de P monedas).
La entrada termina con una máquina con un ciclo de tamaño 0 que no debe procesarse.
Salida
Para cada caso de prueba se escribirá la mayor cantidad de monedas que se pueden conseguir con la máquina de una sola vez, teniendo en cuenta que se pueden jugar tantas partidas consecutivas como se desee. Se puede elegir a partir de qué momento empezar a echar monedas y en qué momento parar, pero no está permitido "saltarse" jugadas una vez que se ha empezado a jugar.
Ten en cuenta que, tras llegar al final, la máquina repite el ciclo. Se garantiza que la máquina siempre da al menos un premio, pero, al mismo tiempo, siempre gana dinero a largo plazo. Es decir, si una persona juega el ciclo completo de la máquina, saldrá perdiendo.
Entrada de ejemplo
9 -1 -1 2 -1 3 -1 -1 -1 -1 9 -1 3 -1 -1 -1 -1 -1 -1 2 9 -1 -1 2 -1 -1 -1 3 -1 -1 0
Salida de ejemplo
4 4 3