TOPIC
PROBLEM 1531 - URI Fórum 1.0
This topic was solved and cannot recieve new replies.
-
crbonilha replied on Mar 3 2014
Essa sua função recursiva leva muito tempo, até para valores baixos. Experimente uma função iterativa quando for calcular algum valor de Fibonacci.
Agora, esse exercício em questão requer uma solução mais elaborada. Fib(N) vai resultar em um valor muito alto, e tirar o Fib() desse resultado vai levar ainda muito mais tempo.
Uma das soluções para este exercício é estudar o Pisano Period (http://en.wikipedia.org/wiki/Pisano_period), e utilizar um método mais eficiente para calcular o Fibonacci (Fast Doubling, ou Exponenciação de Matriz).
-
Ronaldo2 replied 8 years ago
ta dando WA, alguém?
#include<bits/stdc++.h> using namespace std; #define ll long long unsigned int typedef vector<vector<ll> > matrix; ll MODM, MODC; const int K = 2; #define REP(i,n) for (ll i = 1; i <= n; i++) matrix mul(matrix A, matrix B) { matrix C(K+1, vector<ll>(K+1)); REP(i, K) REP(j, K) REP(k, K) C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MODM; return C; } // computes A ^ p matrix pow(matrix A, ll p) { if (p == 1) return A; if (p % 2) return mul(A, pow(A, p-1)); matrix X = pow(A, p/2); return mul(X, X); } // computes A * B matrix mul1(matrix A, matrix B) { matrix C(K+1, vector<ll>(K+1)); REP(i, K) REP(j, K) REP(k, K) C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MODC; return C; } // computes A ^ p matrix pow1(matrix A, ll p) { if (p == 1) return A; if (p % 2) return mul1(A, pow1(A, p-1)); matrix X = pow1(A, p/2); return mul1(X, X); } int main() { ll m, n; matrix T(K+1, vector<ll>(K+1)), M(K+1, vector<ll>(K+1)); while(scanf("%lld%lld", &n, &m) != EOF) { MODM = m; T[1][1] = 0, T[1][2] = 1; T[2][1] = 1, T[2][2] = 1; ll i = 2; while(true) { M = pow(T, i); ll a = M[1][2] % m; M = pow(T, i+1); ll b = M[1][2] % m; if(a == b && a == 1) { break; } i++; } MODC = i - 1; M = pow1(T, n); ll x = M[1][2] % MODC; M = pow(T, x); printf("%lld\n", M[1][2] % MODM); } return 0; } -
andresroliveira replied 7 years ago
Alguem pode me ajudar? To Tomando WA60%. Poderiam postar alguns casos de teste também?
Segue o code:
#include <bits/stdc++.h> #define M 1000000 #define C 1500000 #define P 750000 using namespace std; vector <long long int> f(C+1),fib(P+1); void vet(){ f[1] = f[2] = fib[1] = fib[2] = 1; for(int i=3;i<=P;i++){ f[i] = (f[i-1] + f[i-2]) % M; fib[i] = (fib[i-1] + fib[i-2]) % M; } for(int i=P+1;i<=C;i++){ f[i] = (f[i-1] + f[i-2]) % M; } } int main(){ vet(); int n, m; while(cin >> n >> m){ cout << f[fib[n % P] % C] % m << '\n'; } return 0; } /* fib(n) % m = fib(n % c) % m, para c ciclo de m fib(fib(n)) % m = fib( fib( n % p ) % c ) % m, para p ciclo de c, e c ciclo de m */ -
leodeliyannis replied 8 years ago
Estou tentando submeter o meu código totalmente em C (ou pelo menos, o mais C possível). Mesmo com algumas modificações, ainda tomo Time Limit Exceeded ou Runtime Error. EDIT: Agora estou tomando 80% de Wrong Answer.
Alguma sugestão?
[UPDATE] Accepted. Código removido :DOu ainda, algum bom caso de teste?
Grato.
-
js.100 replied 8 years ago
Talvez seja a sua função fib() que está dando gargalo, por que eu calculei Pisano Period linear (como o Cristhian falou) + Fibonacci Fast Doubling e passei em 0.750s.
-
js.100 replied 8 years ago
Olá, estou recebendo Runtime Error sem nenhum motivo aparente, e o URI não me dá nenhuma informação extra sobre o erro. Qual o limite de memória RAM pra esse problema? Já testei esse código e só precisa de 4MB de RAM pra rodar, inclusive com um arquivo de input bem grande (menos de 4MB dá SegFault).
Código:
Resolvido. -
fnardi replied 8 years ago
Teria como alguém me esclarecer esse problema? Eu implementei fibonacci com potencia de matrizes, o tempo de execução não é o problema, mas como que devo dar a resposta? O enunciado pede: fib(fib(x))%n Mas dessa forma o fib(x) interno vai estourar
Na minha função eu posso passar 2 parametros, X (fib na posicao X) e N (valor para dar Mod em cada etapa da conta) então tentei submeter fib(fib(x),n) mas o fib(x) interno estoura muito rapido, como posso resolver isso? fib(fib(x,n),n) da resposta diferente..
Edit: li a dica do Cristhian, mas agora estou com problema para achar o tamanho do ciclo, a forma iterativa dita faz com que de time limit
-
ffonseca replied 9 years ago
Se você está calculando os n primeiros valores da sequência de Fibonacci, você não precisa calcular eles do zero... Em particular, se você já calculou fib[i] e fib[i+1], calcular fib[i+2] só precisa de uma adição.
-
pmoggi replied 9 years ago
Mesmo seguindo à risca a dica do Cristhian só recebo TLE...
No caso, ele disse que a forma iterativa para encontrar o ciclo, seria suficiente porém:
lli pisano( lli m ) { lli i; ii a; for( i=3; ; i++){ // a = fib(i,m); // if( a.second != 1 ){ // caso fib(i+1)%m nao for 1, continuar i++; continue; } if( a.first == 1) // se fib(i)%m == 1 e fib(i+1)%m == 1, ciclo é o i-1 break; } return --i; }me soa muito custoso // fib(n,m) é a função que retorna um pair (função fast doubling do blog do bonilha) Pensei em armazenar alguns valores baixos da sequencia do fibonacci (sem modulus) num vetor mas nao cheguei a implementa-lo.. Help?
-
ggroth replied 9 years ago
Dê uma olhada nas dicas do Cristhian. http://crbonilha.com/pt/contest-delta-editorial-pt2/#more-97
-
mbrodrigues replied 9 years ago
Alguma sugestão para o meu programa? (submissão #697033) Estou usando o periodo de Pisano para calcular o fib(fib(n))%m, mas meu programa ainda leva alguns segundos para certas entradas(inclusive ja chequei as respostas com o toolkit), o que dá time limit exceeded já que o time limit é 1...
-
cbarreto replied on Apr 2 2014
Por que deu Runtime error ?
#include <stdio.h> unsigned long long fib(int n){ int a = 0, b = 1, c, i; if(n==0) return a; for(i=2;i<=n;i++){ c=a+b; a=b; b=c; } return b; } int main (){ int n, m; unsigned long long fibonacci; while(scanf("%d %d", &n, &m) != EOF){ fibonacci=fib(fib(n))%m; printf("%llu\n", fibonacci); } return 0; }
