Ajuda em problema da URI Online Judge (1531) : Fibbonacci de Novo!

Programação
#1

Gente, bom dia! Eu to fazendo alguns exercicios do uri e travei nesse aqui:

Fibonacci de Novo!

A famosa sequência de Fibonacci pode ser definida da seguinte maneira:

  • Fib( 1 ) = Fib( 2 ) = 1
  • Fib( N ) = Fib( N-1 ) + Fib( N-2 ), para N > 2

Sua tarefa é simples, calcular o valor do resto de Fib( Fib( N ) ) por M.

Entrada

A entrada é composta por vários casos de teste e termina com EOF. Cada caso de teste consiste de uma linha com dois inteiros N e M (1 ≤ N ≤ 109, 2 ≤ M ≤ 106).

Saída

Para cada caso de teste, imprima uma linha contendo um inteiro igual ao resto de Fib( Fib( N ) ) por M .

Exemplo de Entrada Exemplo de Saída
1 100 1
2 100 1
3 100 1
4 100 2
5 100 5
5 2 1
6 100 21

=============================================================================

O meu maior problema é a entrada de vários casos de testes, não sei como se faz isso, só consigo fazer 1 teste de cada vez e acredito que por isso a resposta está errada.




Esse foi o codigo que consegui fazer:

java import java.util.Scanner;


public class Teste {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        if (scan.hasNextInt()) {
            
        
            int N = scan.nextInt();
            int M = scan.nextInt();

            int a = (fib(fib(N))) % M;
            System.out.println(a);
        }
        
        scan.close();
    }

    public static int fib(int x){
        int n1 = 1;
        int n2 = 1;
        int N = 0;

        for(int i = 0; i < x-2; i++){
            N = n1 + n2;
            n1 = n2;
            n2 = N;
        }
    if(x > 2)return(N);
    else return(1);
    }
}

Alguém poder me explicar como faço para resolver o problema dos vários testes?
Obrigado.

#2

O System.in do URI aponta para um arquivo onde cada linha é uma entrada de dados.

Experimenta assim:

import static java.lang.System.out;

import java.util.Scanner;

public class Teste {

    private static final Scanner in = new Scanner(System.in);


    public static void main(String[] args) {

        while (in.hasNextLine()) {
            String linha = in.nextLine();
            String[] numeros = linha.split("\\s");
            int N = Integer.parseInt(numeros[0]);
            int M = Integer.parseInt(numeros[1]);

            int a = (fib(fib(N))) % M;
            out.println(a);
        }
    }

    public static int fib(int x) {
        int n1 = 1;
        int n2 = 1;
        int N = 0;
        for (int i = 0; i < x - 2; i++) {
            N = n1 + n2;
            n1 = n2;
            n2 = N;
        }
        if (x > 2) {
            return N;
        } else {
            return 1;
        }
    }
}
1 curtida
#3

O enunciado da questão está levemente errado! O problema dessa questão é bem maior.

Acredito que as principais dificuldades desse desafio são:

  • O tamanho das entradas, já que a sequência de Fibonacci cresce muito rápido.
  • O tempo para calcular um elemento da sequência.
1 curtida
#4

A leitura em si não é difícil, é só trocar o if por while, como já indicaram acima.

Mas como também foi falado, não adianta simplesmente ir somando os números, pois o valor cresce rápido demais e estoura os limites da linguagem: fib(47) estoura o valor máximo de um int (que é cerca de 2 bilhões) e fib(93) estoura o valor máximo de um long (que é cerca de 9 quintilhões). E depois você ainda precisaria calcular o fib desses números gigantes, cujo resultado seria ainda maior (só para você ter uma ideia, fib(1000000) é um número com mais de 200 mil dígitos - é simplesmente inviável lidar com números dessa magnitude, ainda mais com tempo e memória limitados).

Então teria que ser um algoritmo um pouco mais esperto, já que é dito que N pode ser até 109 (1 bilhão, e não 109 como você disse), ou seja, serão números enormes e mesmo que você use algo como BigDecimal/BigInteger (que suportam valores “gigantes”), ficará tão lento que provavelmente não vai passar (isso se não estourar a memória antes, pois até mesmo essas classes têm limites).

Uma forma de abordar o problema é usar os Pisano Periods: dado um número m, há intervalos que se repetem para a sequência de Fibonacci, se consideramos o resto da divisão de fib(n) por m.

Por exemplo, se tivermos m = 3:

n fib(n) fib(n) % 3
0 0 0
1 1 1
2 1 1
3 2 2
4 3 0
5 5 2
6 8 2
7 13 1
8 21 0
9 34 1
10 55 1
11 89 2

O resultado de fib(n) % 3 começa a se repetir a cada 8 números, então para m=3 o valor do Pisano Period é 8. E o importante é que o período sempre começa com 0 e 1, então não é tão difícil encontrá-lo (basta ir iterando, calculando o resto da divisão e parar quando encontrar 0 e 1).

A partir daí, conclui-se que fib(n) % 3 seria o mesmo que fib(n % pisano_period(3)) % 3.

E portanto fib(fib(n)) % 3 seria fib(fib(n) % pisano_period(3)) % 3.

Já para calcular fib(n) % m, basta ir somando os números e guardar apenas o resto da divisão por m, já que (a + b) % m é igual a ((a % m) + (b % m)) % m (fonte).

Então ficaria assim (chupinhado adaptado daqui):

public static long pisano(long m) {
    long prev = 0;
    long curr = 1;
    long res = 0; 

    for (long i = 0; i < m * m; i++) {
        long temp = curr;
        curr = (prev + curr) % m;
        prev = temp;
        if (prev == 0 && curr == 1) {
            res = i + 1;
            break;
        }
    }
    return res;
}

public static long fibMod(long n, long m) {
    n = n % pisano(m);
    if (n <= 1)
        return n;

    long prev = 0;
    long curr = 1;
    for (long i = 0; i < n - 1; i++) {
        long temp = curr;
        curr = (prev + curr) % m;
        prev = temp;
    }
    return curr % m;
}

public static void main(String args[]) throws IOException {
    Scanner in = new Scanner(System.in);
    while (in.hasNextInt()) {
        int n = in.nextInt();
        int m = in.nextInt();
        System.out.println(fibMod(fibMod(n, pisano(m)), m));
    }
}

Acabei de testar no URI online e passou.

2 curtidas