495 - Fibonacci Freeze

[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]

Modify S[Max][Len] to S[MAX+1][Len] will be fine, just as ezra said.

[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]

it would be as follows then u got Accepted

int S[Max+1][Len+1]={0}; // Set the initial value

[Zhao Le]

I got accept.
Thank you hijbul_ctg.
but i don't understand why,could you tell me?

[Observer]

Hey there.

Is there anything I can do to optimize my program?


Plzzzzzzzzzzz...... (I'm still getting TLE )

[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]

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

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




Thanks a lot!!!!

[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]

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]

/*@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]

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.

[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]

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

[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