10183 - How Many Fibs?

[x140l31]

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]

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]

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]

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

[Moshiur Rahman]

for the input:

Code: Select all

0 2
0 0

your program returns 4. when the correct answer should be 2.

[Obaida]

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!!!

[masud93]

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

void add_zero(char *x,char *y)
{
	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;

}

void add(char *x,char *y)
{
	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)
			add_zero(x,y);
		else if(n1>n2)
			add_zero(y,x);
		add(x,y);
		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]

Because "char sto[100000][100000]" is way too big.

Pls help

"Pls" is not a word! Get a spellchecker.

[sayem]

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

[@mjad]

give me some critical input
to find out WA

[sohel]

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

[sh415]

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...................

[@mjad]

please help me why WA?

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]

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) {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        List<BigDecimal> fibonacciNumber = new ArrayList<BigDecimal>();
        fibonacciNumber.add(BigDecimal.ONE);
        fibonacciNumber.add(BigDecimal.valueOf(2));

        Scanner scanner = new Scanner(reader);


        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));
            fibonacciNumber.add(newFib);
            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]

Input

Code: Select all

0 1
0 0

AC output: 1