10183 - How Many Fibs?

Moderator: Board moderators

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Re: 10183 - How many Fibs?

Can anyone help me?

I don't know why WA!! I've tried all I/O and I get correct answer, except
1 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
because it isn't a correct input, no?
Otherwise, a<=b<=10^100

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Re: 10183 - How many Fibs?

I fix it changing the fib numbers that I calculate to 500

I don't why doesn't work with 475 fib numbers if the 475th number is:

1344719667586153181419716641724567886890850696275767987106294472017884974410332069524504824747437757

that have 101 digits...

it must be that the Input Specification is wrong....

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re:

vijay03 wrote:Can`t binary be used only for searching an exact term? If we use lower_bound and upper_bound, we`ll have to find the smallest fib greater than lower_bound and the highest fib lower than upper_bound and subtract the indices of those two fibs to get the answer right? So how can we use binary search for that?
Here's another idea instead of using binary. Have an array that stores the sequence number of all fib numbers whose length corresponds to the array index. For instance, arr[2] would store the fib sequence number for 13, 21, 34, 55, 89. So if you are given "10 10000", you only need to compare "10" with the ones represented by arr[2] and "10000" with the ones represented by arr[5].

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

Re: 10183 - How many Fibs?

I checked all the test cases in the board seems right.. I thing it's a silly mistake. But i can't figure it out!
Some 1 plz help...

Code: Select all

``removed``
Last edited by Obaida on Sun Feb 15, 2009 1:25 pm, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Moshiur Rahman
New poster
Posts: 13
Joined: Mon Sep 08, 2008 6:57 pm

Re: 10183 - How many Fibs?

for the input:

Code: Select all

``````0 2
0 0
``````
Never think too hard, let ideas come to you...

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

Re: 10183 - How many Fibs?

You know how stupid i am?
I was considering for the input 1. But why i didn't considered it for 0?
This is really a shame!!!
try_try_try_try_&&&_try@try.com
This may be the address of success.

masud93
New poster
Posts: 2
Joined: Thu Jul 23, 2009 8:47 pm

Re: 10183 - How many Fibs?

Why it is Compilation Error.Pls help

Code: Select all

``````#include<stdio.h>
#include<string.h>
char z[100000],a[100000],b[100000],sto[100000][100000];
int flag=0,result=0,k=2;

void reverse(char *x)
{
int i,j,n,temp;
n=strlen(x);
for(i=n-1,j=0;j<n/2;i--,j++)
{
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}

{
int i,j=0,n1,n2;
n1=strlen(x);
n2=strlen(y);
for(i=0;i<n2-n1;i++)
z[i]='0';
while(i<n2)
z[i++]=x[j++];
z[i]='\0';
strcpy(x,z);
}

int compare(char *sto)
{
int n_a,n_b,sum,n_sto,i=0;
if(flag==0)
{
n_a=strlen(a);
n_sto=strlen(sto);
for(i=result=0;a[i];i++)
{
sum=(a[i]-'0')-(sto[i]-'0');
if(sum<0)
{
result=-1;
break;
}
else if(sum>0)
{
result=1;
break;
}
}
}
else
{
n_b=strlen(b);
n_sto=strlen(sto);

if(n_sto>n_b)
result=-1;

else if(n_b>n_sto)
result=1;

else
{
for(i=result=0;b[i];i++)
{
sum=(b[i]-'0')-(sto[i]-'0');
if(sum<0)
{
result=-1;
break;
}
else if(sum>0)
{
result=1;
break;
}
}
}

}
return result;

}

{
int i,carry=0,sum=0,n;
n=strlen(x);
reverse(x);
reverse(y);

for(i=0;x[i];i++)
{
sum=x[i]-'0'+y[i]-'0'+carry;
if(sum>9)
{
sum=sum%10;
carry=1;
}
else
carry=0;
z[i]=sum+'0';
}
if(carry==1)
z[i++]='1';
z[i]='\0';
reverse(z);
strcpy(sto[k++],z);

}
int main()
{
int i,n1,n2,n,count,f;
char x[100000]="1",y[100000]="2";
strcpy(sto[0],x);
strcpy(sto[1],y);

for(i=1;i<=500;i++)
{
n1=strlen(x);
n2=strlen(y);

if(n1<n2)
else if(n1>n2)
reverse(y);
strcpy(x,y);
strcpy(y,z);
}
while(scanf("%s%s",a,b)==2)
{
if(a[0]=='0' && b[0]=='0')
break;
count=flag=f=0;
n1=strlen(a);
for(k=0;;k++)
{
n=strlen(sto[k]);
if(n1==n)
break;
}

for(;;)
{
result=compare(sto[k]);
if(result<=0)
{
for(flag=1;;k++)
{
result=compare(sto[k]);
if(result>=0)
count++;

else
{
f=1;
break;
}
}
}
else
k++;
if(f==1)
break;
}
printf("%d\n",count);
}

return 0;
}

``````

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10183 - How many Fibs?

Because "char sto[100000][100000]" is way too big.
Pls help
"Pls" is not a word! Get a spellchecker.

sayem
New poster
Posts: 7
Joined: Sun Jul 12, 2009 10:30 pm

10183 - How many Fibs?

can u tell why wrong answer?

Code: Select all

``````#include<stdio.h>
#include<string.h>
#include<ctype.h>
#define MAX 1046

void sum(char first[],char sec[],char res[])
{
int f,s,sum,now;
f=strlen(first)-1;
s=strlen(sec)-1;
int x;
if(f>s) now=f;
else now=s;
x=now;
for(sum=0;(f>=0 && s>=0);now--)
{
sum=(first[f]-'0')+(sec[s]-'0')+sum;
res[now]=sum%10+'0';
sum=sum/10;
--f,--s;
}
if(f>=0)
{
for(;f>=0;now--)
{
sum=first[f]+sum-'0';
res[now]=sum%10+'0';
sum=sum/10;
--f;
}
}
else
{
for(;s>=0;now--)
{
sum=sec[s]+sum-'0';
res[now]=sum%10+'0';
sum=sum/10;
--s;
}
}
if(sum!=0)
{
for(int i=x;i>=0;--i)
res[i+1]=res[i];
res[0]=sum+'0';
}
}

int main()
{
int number=3;
char pre_1[MAX],pre_2[MAX];
strcpy(pre_1,"1");
strcpy(pre_2,"2");
char fibo[500][MAX];
strcpy(fibo[1],pre_1);
strcpy(fibo[2],pre_2);
while(strlen(pre_2)<=102)
{
char now[MAX]={" "};
sum(pre_1,pre_2,now);
strcpy(pre_1,pre_2);
strcpy(pre_2,now);
strcpy(fibo[number],pre_2);
++number;
}
char a[MAX],b[MAX];
while(scanf("%s%s",a,b)==2)
{
int i,k=strlen(a),temp=0;
bool flag=false;
for(i=0;i<k;++i)
{
if(!isdigit(a[i]))
{
flag=true;
break;
}
}
if(flag==true) break;
k=strlen(b);
for(i=0;i<k;++i)
{
if(!isdigit(b[i]))
{
flag=true;
break;
}
}
if(flag==true) break;
k=strlen(a);
while(a[temp]=='0') temp++;
for(i=0;temp<k;++i,temp++)
a[i]=a[temp];
a[i]='\0';
k=strlen(b);
temp=0;
while(b[temp]=='0') temp++;
for(i=0;temp<k;++i,temp++)
b[i]=b[temp];
b[i]='\0';
if((strlen(a)>strlen(b))||(strlen(a)==strlen(b) && strcmp(a,b)>0))
{
char t[1000];
strcpy(t,a);
strcpy(a,b);
strcpy(b,t);
}
if(strlen(b)==102 && strcmp(b,"100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000")==0);
else if(strlen(b)==0 || strlen(a)>101 || strlen(b)>101) break;
int num=0;
for(i=1;i<=number;++i)
{
if(strlen(a)<=strlen(fibo[i]) && strlen(b)>=strlen(fibo[i]))
{
if(strlen(a)==strlen(fibo[i]) && strcmp(a,fibo[i])>0)
continue;
if(strlen(b)==strlen(fibo[i]) && strcmp(b,fibo[i])<0)
break;
num++;
}
}
printf("%d\n",num);
}
return 0;
}
``````

New poster
Posts: 44
Joined: Thu Jul 22, 2010 9:42 am

give me some critical input
to find out WA
Last edited by @mjad on Tue Oct 12, 2010 7:56 pm, edited 1 time in total.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 10183 CE? any body help me pleaseee

You should be able to see the reason for compile error by clicking on 'compile error' message in the submission page!

sh415
New poster
Posts: 13
Joined: Fri Nov 13, 2009 9:31 am
Location: JU

Re:

Caesum wrote:Can anyone confirm the following input:
10 100
1234567890 9876543210
3 5
5 8
0 1
1 2
0 2
0 7
298611126818977066918552 483162952612010163284885
1 36726740705505779255899443
8 12
8 13
1 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
21 1
0 0
gives the following output:
5
4
2
2
1
2
2
4
2
123
1
2
483
7
there is no such input such that 21 1
the input must be 1 21................
yeh; except last one my AC code gives same output...................

New poster
Posts: 44
Joined: Thu Jul 22, 2010 9:42 am

Code: Select all

``````#include<iostream.h>

#include<string.h>
//using namespace std;

int compare(char a[100009],char b[100009]);
void sum(char a[100009],char b[100009]);
void fact(char f1[100009],char f2[100009]);
char f1[100009],f2[100009];
long z;
int main()
{
char first[100009],second[100009];
int n;
int i;

//freopen("test.txt","r",stdin);
while(1){
cin>>first>>second;
if(first[0]-48==0&&second[0]-48==0)
break;
fact(first,second);
}

return 0;

}
void fact(char first[100009],char second[100009])
{

long count=0,m,n=0;
f1[0]='1';
f2[0]='2';
f2[1]=f1[1]='\0';
m=compare(first,second);
if(m==2||m==1)
return ;
do
{

if(n==0){
m=compare(f1,first);
if(m==1){
m=compare(f1,second);
if(m==0)
{
count++;
n++;
}
}

}
sum(f1,f2);
m=compare(f1,second);
if(n!=0&&m==0)
count++;
} while(m!=1&&m!=2);
if(n!=0)
cout<<count<<endl;
return ;
}
void sum(char a[100009],char b[100009])
{
char num[100009],num2[100009],result[100009];
long l1,l2,carry=0,index=0,t,i,j=0;
l1=strlen(a);
l2=strlen(b);
if(l1>=l2){
strcpy(num,a);
strcpy(num2,b);
}
else{
strcpy(num,b);
strcpy(num2,a);
l1=l2;
}
l2=strlen (num2);
while(l2)
{
l2--;l1--;
t=(num[l1]-48)+(num2[l2]-48)+carry;
result[index++]=t%10+48;
carry=t/10;

}

if(l1!=0)
while(l1)
{
l1--;
t=(num[l1]-48)+carry;
result[index++]=(t%10)+48;
carry=t/10;
}

if(carry)
result[index++]=carry+48;;
result[index++]='\0';
strcpy(f1,f2);
for(i=index-2;i>=0;i--)
f2[j++]=result[i];
f2[j++]='\0';
return ;
}

int compare(char first[100009],char second[100009])
{
int i,l1,l2;
l1=strlen(first);
l2=strlen(second);
if(l1>l2)
return 1;
if(l2>l1)
return 0;

for(i=0;i<l1;i++){
if((first[i]-48)>(second[i]-48))
return 1;
if((first[i]-48)<(second[i]-48))
return 0;
}

return 2;
}

``````

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 10183 - How many Fibs?

Hello
Why I'am getting WA

Code: Select all

``````import java.io.*;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Main {

public static void main(String[] args) {

BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

List<BigDecimal> fibonacciNumber = new ArrayList<BigDecimal>();

BigDecimal maxValue = BigDecimal.valueOf(10).pow(100);
int index = 2;
BigDecimal newFib = BigDecimal.ZERO;
while (newFib.compareTo(maxValue) <= 0) {
newFib = fibonacciNumber.get(index - 1).add(fibonacciNumber.get(index - 2));
index++;
}

try {
BigDecimal first;
BigDecimal second;

while (!(first = new BigDecimal(scanner.next())).equals(BigDecimal.ZERO) && !(second = new BigDecimal(scanner.next())).equals(BigDecimal.ZERO)) {
int start = 0;
int end = 0;

for (int i = 0; i < fibonacciNumber.size(); i++) {
BigDecimal bigDecimal = fibonacciNumber.get(i);
if (first.compareTo(bigDecimal) <= 0) {
start = i;
break;
}
}

for (int i = start; i < fibonacciNumber.size(); i++) {
BigDecimal bigDecimal = fibonacciNumber.get(i);
if (second.compareTo(bigDecimal) <= 0) {
end = i;
break;
}
}
int result = end - start;
if (fibonacciNumber.get(start).equals(first) && fibonacciNumber.get(end).equals(second)) {
result++;
}
writer.write(Integer.valueOf(result).toString());
writer.write("\n");
}
writer.flush();
} catch (IOException e) {
}
}
}
``````

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

Re: 10183 - How many Fibs?

Input

Code: Select all

``````0 1
0 0``````
AC output: 1
Check input and AC output for thousands of problems on uDebug!