10183 - How Many Fibs?

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

Moderator: Board moderators

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

Re: 10183 - How many Fibs?

Post by x140l31 » Sat Aug 02, 2008 9:24 pm

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?

Post by x140l31 » Sat Aug 02, 2008 9:24 pm

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:

Post by stcheung » Tue Oct 07, 2008 7:33 am

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
Location: (BUBT) Dhaka,Bagladesh.

Re: 10183 - How many Fibs?

Post by Obaida » Thu Feb 12, 2009 7:20 am

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

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
Location: State University of Bangladesh

Re: 10183 - How many Fibs?

Post by Moshiur Rahman » Sat Feb 14, 2009 5:53 pm

for the input:

Code: Select all

0 2
0 0
your program returns 4. when the correct answer should be 2.
Never think too hard, let ideas come to you...

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10183 - How many Fibs?

Post by Obaida » Sun Feb 15, 2009 1:37 pm

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!!! :oops:
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?

Post by masud93 » Thu Jul 30, 2009 10:08 am

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10183 - How many Fibs?

Post by mf » Thu Jul 30, 2009 10:43 am

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?

Post by sayem » Mon Aug 03, 2009 2:56 am

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
New poster
Posts: 44
Joined: Thu Jul 22, 2010 9:42 am

10183 why worng answer?

Post by @mjad » Thu Jul 29, 2010 7:47 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.

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

Re: 10183 CE? any body help me pleaseee

Post by sohel » Thu Jul 29, 2010 8:55 pm

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:

Post by sh415 » Mon Sep 06, 2010 4:07 am

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

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

Re: 10183 why worng answer?

Post by @mjad » Thu Nov 04, 2010 3:59 am

:( 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
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 10183 - How many Fibs?

Post by sith » Sun Jul 01, 2012 7:59 pm

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

Re: 10183 - How many Fibs?

Post by brianfry713 » Mon Jul 02, 2012 9:59 pm

Input

Code: Select all

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

Post Reply

Return to “Volume 101 (10100-10199)”