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

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Thank you, but that not work.I still got RTE.

Post by Zhao Le »

if you declare your array 5000 that means the index is between 0-4999.
if the input is 5000 then your code try to read index 5000 which is illegal.
i think thats why you got RTE.
i don't understand, simply don't understand.
i print 5000 and it seems right.
who can test it for me?
just sumbit to the online judge.
and may know what problem i may occur.

Thank you all.
LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn »

Modify S[Max][Len] to S[MAX+1][Len] will be fine, just as ezra said.
Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

I have tried.

Post by Zhao Le »

Modify S[Max][Len] to S[MAX+1][Len] will be fine, just as ezra said
.
I have tried.
but still got RTE.
hijbul_ctg
New poster
Posts: 8
Joined: Sat Apr 19, 2003 5:41 pm
Contact:

Post by hijbul_ctg »

it would be as follows then u got Accepted

int S[Max+1][Len+1]={0}; // Set the initial value
Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

finally i got accept.

Post by Zhao Le »

I got accept.
Thank you hijbul_ctg.
but i don't understand why,could you tell me?
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

Hey there.

Is there anything I can do to optimize my program?


Plzzzzzzzzzzz...... (I'm still getting TLE :cry: )
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Using write to produce output in pascal is extremely slow. Assemble all output for one line in an ansistring and do one writeln.

Change
[pascal] for n := k downto 1 do
write(ans[i,n]);
writeln;[/pascal]
To
[pascal] setlength(line,k);
for n := k downto 1 do
line[k-n+1]:=chr(ans[i,n]+ord('0'));
writeln(line); [/pascal]
where var line:ansistring;

That way you'll get AC in less than a second!

PS: please remove your code now, 'cause it's a spoiler :)
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

(......I've never thought of that.......)

WOW!!!!!!!!!! It works!!!!!!




Thanks a lot!!!! :lol: :lol: :lol: :lol: :lol: :lol:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
User avatar
kenny1har
New poster
Posts: 7
Joined: Fri May 09, 2003 2:30 am

495 - can anybody help me ?

Post by kenny1har »

i don't understand why my program is wrong
please give any comments ....

how about the output format for a very big number (with exponential ?)

[pascal]
program p495 (input, output);
var
n,j :integer;
x,y,z,temp:extended;
begin
while not eof(input) do begin
readln(n);
x:=1;
y:=1;
if n=0 then z:=0 else z:=1;
for j:=3 to n do begin
z:=x+y;
temp:=y;
y:=z;
x:=temp;
end;
writeln('The Fibonacci number for ',n,' is ',z:0:0);
end;
end.
[/pascal]
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

First look at the previous posts before starting a new thread!
It is somewhere stated that the 5000th fibo has more than 1000 digits, your program doesn't even come close.
jubayer
New poster
Posts: 1
Joined: Sat May 31, 2003 5:16 am

495-fibonacci freeze why it is time limit exceed

Post by jubayer »

/*@JUDGE_ID:16408FF 495 C++*/
/*@BEGIN_OF_SOURCE_CODE*/
#include <stdio.h>
#include <string.h>
void stradd(char num1[], char num2[], char result[])
{
char c;
int i, j, k, carry;
k=carry=0;
for(i=strlen(num1)-1, j=strlen(num2)-1;i>=0&&j>=0;i--, j--)
{
result[k++]=((carry+((num1-'0')+(num2[j]-'0')))%10)+'0';
carry=(carry+(num1-'0')+(num2[j]-'0'))/10;
}

while(i>=0){
if(carry>0)
{
result[k++]=((carry+(num1-'0'))%10)+'0';
carry=(carry+(num1-'0'))/10;
i--;
}
else
result[k++]=num1[i--];
}
while(j>=0)
{
if(carry>0)
{
result[k++]=((carry+(num2[j]-'0'))%10)+'0';
carry=(carry+(num2[j]-'0'))/10;
j--;
}
else
result[k++]=num2[j--];
}
if(carry>0)result[k++]=(carry+'0');
result[k]='\0';
for(i=0, j=strlen(result)-1;i<j;i++, j--)
c=result, result=result[j], result[j]=c;
}
int main()
{
int n, count;
char f1[10000], f2[10000], temp[20000];
while(scanf("%d", &n)==1){
f1[0]='1';f1[1]='\0';
f2[0]='1';f2[1]='\0';
if(n<3)printf("The Fibonacci number for %d is 1\n", n);
else
{
for(count=1;count<=n-2;count++)
{
stradd(f1, f2, temp);
strcpy(f1, f2);
if(count==n-2)break;
strcpy(f2, temp);
}
printf("The Fibonacci number for %d is %s\n", n, temp);
}
}
return 0;
}
/*@END_OF_SOURCE_CODE*/
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel »

First I tried to solve it using your technique and got TLE.

Try to store all the answers before considering inputs.
And then simply print("The xxxxxxxxxx is %s",fib[n]);

Hope it helps.
Last edited by sohel on Mon Dec 01, 2003 9:52 am, edited 1 time in total.
hijbul_ctg
New poster
Posts: 8
Joined: Sat Apr 19, 2003 5:41 pm
Contact:

Post by hijbul_ctg »

the name of problem the Fibonacci Freeze . So you have to freeae/store it. becasue for 5000th fib u need to genarate upto 4999'th and so on. So there is repeating. What will be the conditon if 5000 have 100 times in judge input. No doubt that it will cause TLE
Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Post by Master »

I got AC with this problem

I use a precalculation to find all the number and use dynamic memory allocation in that case.


M H Rasel
CUET Old Sailor
User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

495,over flow cant help

Post by Riyad »

i dont understand which data type to use . i used long double i guess which is not enough .pliz help me . here is my code

#include<stdio.h>

#define size 6005

long double result[size];

int index=0;

void init(){

register int i;
for(i=2;i<size;i++){

result=0;
}
result[0]=0;
result[1]=1;
index=2;


}

void compute(){

long double lofib=0,hifib=1,x;

register int i ;

init();
for(i=2;i<=5500;i++){

x=lofib;
lofib=hifib;
hifib=x+lofib;
result[index++]=hifib;

}
result[index++]=hifib;


}

int main(){

int n;

compute();
freopen("input.in","rt",stdin);

while(scanf("%d",&n)==1){

printf("The Fibonacci number for %d is %.0Lf\n",n,result[n]);


}

return 0;

}

plizzzz help me . thanx in advance
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN
Post Reply

Return to “Volume 4 (400-499)”