Title: Ganhando o prêmio maior da caça-níquel
Course: Introdução à Ciência de Computação - 2016 > Section: 25 November - 02 December

Para cada rodada i, uma caça-níquel tem o seguinte programa de premiação:

- Se é apostado um número n ímpar de moedas, elas serão duplicadas;
- Se a quantidade de moedas n é um número par, então:
  - O valor total obtido do prêmio será a diferença absoluta dos números pares e ímpares na sequência inversa Fibonacci de base n e n-i "inv(F_n,n-i)" se n-i é maior do que 0;
  - Caso contrario, se n-i é menor ou igual do que 0, o valor do prêmio será a metade das moedas.

Nas seguintes rodadas, o comportamento de premiação será repetido com n sendo todo o montante acumulado de moedas. No entanto, se n é um múltiplo de 5 ou ele for maior do que 10000 moedas na rodada, todo o montante será perdido na próxima rodada. Assim, para uma aposta inicial de n=13, a seguinte sequência de premiação da caça níquel será obtida:
26, 74, 68, 196, 186, 546, 532, 1580,0, 0, ....

Escreva um programa, que dado dois números inteiros min e max, os quais representam respectivamente o mínimo e máximo de moedas que podem ser apostadas no início do jogo, determine: o valor de n no intervalo de min e max (incluindo min e max) que devemos apostar no início do jogo para ganhar o prêmio maior, o número i de iterações (rodadas) necessárias para ganhar esse prêmio e o valor do prêmio maior. No máximo podem ser feitas 100 rodadas por jogo (i<=100), a rodada 101 não existe.

Importante:

- O prêmio maior é o máximo beneficio que podemos sacar da caça-níquel com o programa de premiação detalhado acima.

Dicas:

- A sequência inversa Fibonacci de base n e m "inv(F_n,m)" é a sequência de números inteiros positivos na qual cada termo sub-sequente corresponde à diferença dos dois números anteriores. Por exemplo, para n=81 e m=50, a sequência inversa Fibonacci é 81, 50, 31, 19, 12, 7, 5, 2, 3.
- Para calcular o valor absoluto de um número x, uma solução básica é multiplicar o número por -1 se x é menor do que 0 (zero).

Entrada e Saída:

A entrada será constituída por dois números inteiros min e max, ambos maiores do que 0 e menores que 10000. A entrada min será sempre menor do que max e cada linha no arquivo "input.txt" representará uma entrada para o programa.

Como saída, você deve imprimir cinco números, os valor de min, o valor de max, o valor n a ser apostado para ganhar o prêmio maior, a iteração na qual devemos parar para ganhar o prêmio maior e o valor do prêmio maior. Veja abaixo alguns exemplos de entrada/saída:

Exemplos de entrada | Saída para os exemplos de entrada
5 13 | 5 13 13 8 1580
8 20 | 8 20 17 8 2228
2 18 | 2 18 17 8 2228
3 23 | 3 23 23 8 3200
1 9999 | 1 9999 4999 2 29990