495 - Fibonacci Freeze

[amafhh535]

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.
Please help me.

[brianfry713]

Post your full code.

[amafhh535]

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]

It is difficult to guess why your code is getting TLE without seeing the full code you'd actually submit.

[amafhh535]

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

[brianfry713]

When I tried to submit that code I get the error:
Code length can't be over 40 kilobytes

[amafhh535]

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

[brianfry713]

When I tried to submit that code I get the error:
Code length can't be over 40 kilobytes

[samoel_stt]

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;
}
void anadirDerecha(TLista* lista, int elem){
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;
}
}
void anadirIzquierda(TLista* lista, int elem){
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)
anadirIzquierda(lista,acc);
}
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;
anadirIzquierda(listaSum,num1+num2);
ptrRec1 = ptrRec1->ant;
ptrRec2 = ptrRec2->ant;
}
while (ptrRec1 != NULL){
anadirIzquierda(listaSum,ptrRec1->dig);
ptrRec1 = ptrRec1->ant;
}
while (ptrRec2 != NULL){
anadirIzquierda(listaSum,ptrRec2->dig);
ptrRec2 = ptrRec2->ant;
}
arreglarLista(listaSum);
}
TLista fibo[MAX];
void inicializa(TLista fibo[MAX]){
TLista lista1,lista2;
listaNueva(&lista1);
listaNueva(&lista2);
anadirDerecha(&lista1,0);
fibo[0] = (lista1);
anadirDerecha(&lista2,1);
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]

Fibonacci not Fibonnaci

[samoel_stt]

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

[brianfry713]

Try doing a diff against the sample output and you'll catch mistakes like that.

[the_mez]

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;
}
string add(string small,string large)
{
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++)
{
series=add(series[i-2],series[i-1]);
}
cout<< "The Fibonacci number for "<<no<<" is "<<series[no]<<endl;
}

return 0;
}