## 495 - Fibonacci Freeze

Moderator: Board moderators

amafhh535
New poster
Posts: 4
Joined: Thu Jul 04, 2013 3:55 pm

### 495 - Fibonacci Freeze - TLE

this my code:

Code: Select all

``````BigInteger fibo[5010];
int main()
{
int input;
fibo[0] = 0;
fibo[1] = 1;
for(int i=2 ; i<5001 ; ++i)
{
fibo[i] = fibo[i-1]+fibo[i-2];
}

while(cin>>input)
cout<<"The Fibonacci number for "<<input<<" is "<<fibo[input]<<endl;
return 0;
}``````
But i don't know why i get TLE.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 495 - Fibonacci Freeze - TLE

Check input and AC output for thousands of problems on uDebug!

amafhh535
New poster
Posts: 4
Joined: Thu Jul 04, 2013 3:55 pm

### Re: 495 - Fibonacci Freeze - TLE

this my full code.only i don't write my include.
this my full code:

Code: Select all

``````#include<iostream>
#include<string>
#include"BigIntegerLibrary.h"
using namespace std;
BigInteger fibo[5010];
int main()
{
int input;
fibo[0] = 0;
fibo[1] = 1;
for(int i=2 ; i<5001 ; ++i)
{
fibo[i] = fibo[i-1]+fibo[i-2];
}

while(cin>>input)
cout<<"The Fibonacci number for "<<input<<" is "<<fibo[input]<<endl;
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 495 - Fibonacci Freeze - TLE

It is difficult to guess why your code is getting TLE without seeing the full code you'd actually submit.
Check input and AC output for thousands of problems on uDebug!

amafhh535
New poster
Posts: 4
Joined: Thu Jul 04, 2013 3:55 pm

### Re: 495 - Fibonacci Freeze - TLE

full code's link that i submit:
http://ideone.com/GI3Rh2

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 495 - Fibonacci Freeze - TLE

When I tried to submit that code I get the error:
Code length can't be over 40 kilobytes
Check input and AC output for thousands of problems on uDebug!

amafhh535
New poster
Posts: 4
Joined: Thu Jul 04, 2013 3:55 pm

### Re: 495 - Fibonacci Freeze - TLE

i reduce my code less than 40 KB.
only write some line in one line.
http://ideone.com/gs2Agf

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 495 - Fibonacci Freeze - TLE

When I tried to submit that code I get the error:
Code length can't be over 40 kilobytes
Check input and AC output for thousands of problems on uDebug!

samoel_stt
New poster
Posts: 8
Joined: Mon Jun 16, 2014 11:59 pm

### Re: 495 - Fibonacci Freeze

I tried solving this problem using double linked list but i get WA . The procedures "anadirDerecha" and "anadirIzquierda" means adding elements at the end and beginning of the list respectively. The process "suma" means adding elements from two list and saving it in the list listaSum and it uses and auxiliary process called "arreglarLista" where it fixes the list when there is a digit greater than 9 in it. I used and array of pointer to lists to have all the numbers.
Here´s the code:
If the code doesn´t display correctly, here's a pastebin from it: http://pastebin.com/Fkexjust

#include <stdio.h>
#include <stdlib.h>
#define MAX 5001
typedef struct nodo{
int dig;
struct nodo* ant;
struct nodo* sig;
}TNodo;
typedef struct lista{
TNodo *ini;
TNodo *fin;
}TLista;

void listaNueva(TLista* lista){
lista->ini = NULL;
lista->fin = NULL;
}
TNodo* nodo;
nodo=(TNodo*)malloc(sizeof(TNodo));
nodo->dig = elem;
if (lista->ini == NULL && lista->fin == NULL){
nodo->ant = NULL;
nodo->sig = NULL;
lista->ini = nodo;
lista->fin = nodo;
}else {
nodo->ant = lista->fin;
lista->fin->sig = nodo;
nodo->sig = NULL;
lista->fin = nodo;
}
}
TNodo* nodo;
nodo = (TNodo*)malloc(sizeof(TNodo));
nodo->dig = elem;
if (lista->ini == NULL && lista->fin == NULL){
nodo->ant = NULL;
nodo->sig = NULL;
lista->ini = nodo;
lista->fin = nodo;
} else {
nodo->ant = NULL;
nodo->sig = lista->ini;
lista->ini->ant = nodo;
lista->ini = nodo;
}
}
void arreglarLista(TLista* lista){
TNodo *ptrRec;
ptrRec = lista->fin;
int acc = 0;
while (ptrRec != NULL){
if (ptrRec->dig > 9){
ptrRec->dig = (ptrRec->dig) - 10 + acc;
acc = 1;
}else{
ptrRec->dig = ptrRec->dig + acc;
if (ptrRec->dig > 9){
ptrRec->dig = 0;
acc = 1;
}else acc = 0;
}
ptrRec = ptrRec->ant;
}
if(acc == 1)
}
void imprimeLista(TLista* lista){
TNodo* rec;
rec = lista->ini;
while (rec != NULL){
printf("%d",rec->dig);
rec = rec->sig;
}
printf("\n");
}
void suma(TLista* listaSum,TLista *lista1, TLista *lista2){
TNodo *ptrRec1, *ptrRec2;
ptrRec1 = lista1->fin;
ptrRec2 = lista2->fin;
while (ptrRec1 != NULL && ptrRec2 != NULL){
int num1, num2;
num1 = ptrRec1->dig;
num2 = ptrRec2->dig;
ptrRec1 = ptrRec1->ant;
ptrRec2 = ptrRec2->ant;
}
while (ptrRec1 != NULL){
ptrRec1 = ptrRec1->ant;
}
while (ptrRec2 != NULL){
ptrRec2 = ptrRec2->ant;
}
arreglarLista(listaSum);
}
TLista fibo[MAX];
void inicializa(TLista fibo[MAX]){
TLista lista1,lista2;
listaNueva(&lista1);
listaNueva(&lista2);
fibo[0] = (lista1);
fibo[1] = (lista2);
int i;
for(i=2;i<MAX;i++){
listaNueva(&fibo);
suma(&fibo,&fibo[i-1],&fibo[i-2]);
}
}
int main(int argc, char** argv) {
inicializa(fibo);
int elem;
for( ;; ){
if (scanf("%d",&elem) == EOF) break;
printf("The Fibonnaci number for %d is ",elem);
imprimeLista(&fibo[elem]);
}
return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 495 - Fibonacci Freeze

Fibonacci not Fibonnaci
Check input and AC output for thousands of problems on uDebug!

samoel_stt
New poster
Posts: 8
Joined: Mon Jun 16, 2014 11:59 pm

### Re: 495 - Fibonacci Freeze

OMG hahaha you´re right! I got accepted I think i will get a new pair of glasses haha Thank you!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 495 - Fibonacci Freeze

Try doing a diff against the sample output and you'll catch mistakes like that.
Check input and AC output for thousands of problems on uDebug!

the_mez
New poster
Posts: 2
Joined: Sun Jun 05, 2016 4:35 pm

### Re: 495 - Fibonacci Freeze

i am getting TLE in uva-495..any help?

#include<iostream>
#include<string>
using namespace std;
string rev(string tmp)
{
char x;
for(int i=0,j=tmp.length()-1;i<j;i++,j--)
{
x=tmp;
tmp=tmp[j];
tmp[j]=x;
}

return tmp;
}
{
int smlen=small.length()-1;
int lrglen=large.length()-1;
int a,b,sum,temp,carry=0;
string result="";
while(lrglen>=0)
{

if(large.length()-lrglen>small.length())
{

a=large[lrglen]-'0';
sum=a+carry;
if(sum>9)
{
carry=1;
temp=sum%10;
result+=temp+'0';
}
else
{
result+=sum+'0';
carry=0;
}
}

else
{
a=large[lrglen]-'0';
b=small[smlen]-'0';
sum=a+b+carry;
if(sum>9)
{
//cout<<"here"<<endl;
carry=1;
temp=sum%10;
result+=temp+'0';

}
else
{
result+=sum+'0';
carry=0;
}

}
lrglen--;
smlen--;

}

if(lrglen<0 && carry==1)
result+='1';
result=rev(result);
return result;
}

int main()
{
int no;

while(cin>>no)
{
string series[no+1];
series[0]="0";
series[1]="1";

for(int i=2;i<=no;i++)
{