495 - Fibonacci Freeze

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

495 - Fibonacci Freeze - TLE

Post by amafhh535 » Wed Jul 31, 2013 2:13 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 495 - Fibonacci Freeze - TLE

Post by brianfry713 » Thu Aug 01, 2013 12:11 am

Post your full code.
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

Post by amafhh535 » Thu Aug 01, 2013 12:34 pm

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

Post by brianfry713 » Fri Aug 02, 2013 12:43 am

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

Post by amafhh535 » Fri Aug 02, 2013 6:01 am

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

Post by brianfry713 » Fri Aug 02, 2013 11:37 pm

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

Post by amafhh535 » Sat Aug 03, 2013 5:48 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 495 - Fibonacci Freeze - TLE

Post by brianfry713 » Tue Aug 06, 2013 1:27 am

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

Post by samoel_stt » Tue Jun 17, 2014 12:26 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 495 - Fibonacci Freeze

Post by brianfry713 » Tue Jun 17, 2014 7:38 pm

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

Post by samoel_stt » Tue Jun 17, 2014 9:48 pm

OMG hahaha you´re right! I got accepted :D 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

Post by brianfry713 » Wed Jun 18, 2014 7:37 pm

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

Post by the_mez » Sun Jun 05, 2016 4:41 pm

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;
}

Post Reply

Return to “Volume 4 (400-499)”