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

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Tue Feb 18, 2003 2:41 am

Hello, when I got "compiler-error" result ... I always looked into the email sent back to me. It has pretty useful description about what the culprit might be.

What was yours ??? Did you enable the option to receive email back ???

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Tue Feb 18, 2003 2:49 am

Well, I took your code and compile it using gcc. Definitely it breaks somewhere ... You should be able to spot it yourself man ...

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

razibcse
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Location: SUST,BANGLADESH
Contact:

Thanx a lot

Post by razibcse » Fri Feb 21, 2003 8:15 pm

Thanx man for ur time to see my code...
I made a mistake in the typecasting where I forgot to give parentheses...Totally silly....

Then I got Accepted...495 & 10183...

thanx again...

Razib

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

10183 (wa),plizzzzzzzzzzzz help :(:(

Post by Riyad » Thu Aug 21, 2003 9:50 am

i generated 550 th fib . bocz 500 th fib contains 105 digits.than i tried to search the extreme points and subtract to get the ans . i used the big integer class to create the fibonaci numbers , i got ac on 495 by using the same class. but i am getting wa all the time with 10183. plizzzz help me .here is my code , sorry as it is big and clumsy .
:cry: :cry: :cry: :cry: :cry: :cry:
.

[cpp]

Code: Select all

#include <iostream.h> 
#include <stdio.h> 
#include <ctype.h> 
#include <math.h> 
#include <string.h> 





	int BigIntMajorVersion = 6; 
	int BigIntMinorVersion = 7; 
	int BigIntRevision = 25; 

	typedef unsigned int SizeT; 
	typedef unsigned int DATATYPE; 

	const DATATYPE BASE = 10000; 
	const DATATYPE INVALIDDATA = 65535U; 
	const SizeT LOG10BASE = 4; 
  
  
  class BigInteger 
  { 
  private: 
    DATATYPE *TheNumber; 
    SizeT Start; 
    SizeT End; 
    bool isNegative; 

    BigInteger(SizeT,DATATYPE,bool); 

    void datacopy(BigInteger const&,SizeT); 

    SizeT datalen(DATATYPE const*) const; 
    void deallocateBigInteger(); 
    void TrimZeros(); 
    void Set(DATATYPE); 

  public: 
    BigInteger(); 
    BigInteger(long); 
    BigInteger(char const*); 
    BigInteger(BigInteger const&); 

    ~BigInteger(); 

    int UnsignedCompareTo(BigInteger const&)const; 
    int CompareTo(BigInteger const&)const; 

    SizeT Digits() const; 
    bool isValidNumber() const; 
    bool isZero()const; 

    BigInteger& Add(BigInteger const&) const; 
    BigInteger& Subtract(BigInteger const&) const; 
    BigInteger& Multiply(BigInteger const&) const; 
    BigInteger& Multiply(DATATYPE const&) const; 
    BigInteger& DivideAndRemainder(BigInteger const&,BigInteger&,bool) const; 
    BigInteger& DivideAndRemainder(DATATYPE const&,DATATYPE&,bool) 

const; 


    friend BigInteger& operator+(BigInteger const&, BigInteger const&); 
	friend BigInteger& operator-(BigInteger const&, BigInteger const&); 
    friend BigInteger& operator*(BigInteger const&, BigInteger const&); 
    friend BigInteger& operator*(BigInteger const&, DATATYPE const&); 
    friend BigInteger& operator*(DATATYPE const&, BigInteger const&); 
    friend BigInteger& DivideAndRemainder(BigInteger const&, BigInteger 

const&,BigInteger&,bool); 
    friend BigInteger& DivideAndRemainder(BigInteger const&, DATATYPE 

const&,DATATYPE&,bool); 
    friend BigInteger& operator/(BigInteger const&, BigInteger const&); 
    friend BigInteger& operator/(BigInteger const&, DATATYPE const&); 
    friend BigInteger& operator/(DATATYPE const&, BigInteger const&); 
    friend BigInteger& operator%(BigInteger const&, BigInteger const&); 
    friend BigInteger& operator%(BigInteger const&, DATATYPE const&); 
    friend BigInteger& operator%(DATATYPE const&, BigInteger const&); 

    BigInteger& operator=(BigInteger const&); 

    friend ostream& operator<<(ostream& ,  BigInteger const&); 
    friend istream& operator>>(istream& , BigInteger& ); 


    BigInteger& operator++(); 
    BigInteger& operator++(int); 

    BigInteger& operator--(); 
    BigInteger& operator--(int); 

    BigInteger& operator-(); 


    BigInteger& operator<<(SizeT); 
    BigInteger& operator>>(SizeT); 
    void abs(); 
    friend BigInteger& abs(BigInteger&); 

    int toInt(); 
    long toLong(); 

    BigInteger& Power(long )const; 
    BigInteger& SquareRoot() const; 
  }; 


BigInteger zero("0"), one("1");

BigInteger fib[555];


int check(BigInteger &x){

	int  i;
	for(i=0;i<=550;i++){
	
		if(x>fib[i])
			continue;
		else
			break;
	
	}

	return i;

}


void create(){
	
	register int i;

	fib[0] = zero;
	fib[1] = one;

	
	for(i = 2; i <= 550; i++)
	{
		fib[i] = fib[i-1] + fib[i-2];
	}



}



int main(){


	register  int count;
	char a[1500],b[1500];
	
	
	
	//freopen("input.in","rt",stdin);	

	create();	

	
	while(scanf("%s %s",a,b)==2){
	
		if(strcmp(a,"0")==0 && strcmp(b,"0")==0)
			break;
		BigInteger t1(a),t2(b);
		
		count=check(t2)-check(t1);
			
	
		printf("%d\n",count);
	
	
	}
	
	return 0;

	
	

}
[/cpp]
plizzzzzzzzzzzzzzzzz seeking for help
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Thu Aug 21, 2003 3:42 pm

For each test case output on a single line the number of Fibonacci numbers fi with a<=fi<=b.
What if a == b and a is a Fibonacci number. I think your program reports 0, and the answer should be 1.

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

got it ac

Post by Riyad » Thu Aug 21, 2003 8:37 pm

thanx a lot . got it ac at last . thanx for u r help .
Bye
Riyad :P :P :P :P :P :lol: :lol: :D :D
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

aakash_mandhar
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore

10183 WA Help

Post by aakash_mandhar » Mon Jan 19, 2004 9:13 pm

HI I solved 495 using the similar method. But now i am getting wa.. I tested or the case of a==b and a being fib no also.. can anyone plz help me out..

[cpp]
# include<iostream.h>
# include<string.h>
# include<stdlib.h>

char *aa[501];


char a[1000],b[1000],c[1000];
char s1[1000],s2[1000],s3[1000];

int ac,bc,cc,uc;
int n;

void add()
{
int i,carry=0;
cc=0;
for(i=0;i<ac && i<bc;i++)
{
c[cc]=((a+b+carry-'0'-'0')%10)+'0';
carry=(a+b-'0'-'0'+ carry)/10;
cc++;
}

for(;i<ac;i++)
{
c[cc]=((a+carry-'0')%10)+'0';
carry=((a-'0'+carry)/10);
cc++;
}

for(;i<bc;i++)
{
c[cc]=((b+carry-'0')%10)+'0';
carry=((b-'0'+carry)/10);
cc++;
}

while(carry)
{
c[cc++]=(carry%10)+'0';
carry/=10;
}

c[cc]='\0';
}

void mystrrev(char *a)
{
char temp;
for(int i=0;i<strlen(a)/2;i++)
{
temp=a;
a=a[strlen(a)-i-1];
a[strlen(a)-i-1]=temp;
}
}

int main()
{
int j,mys,t1;
aa[0]=new char[2];
strcpy(aa[0],"0");
aa[1]=new char[2];
strcpy(aa[1],"1");
ac=1;
bc=1;
strcpy(a,aa[0]);
strcpy(b,aa[1]);
for(j=2;j<=500;j++)
{
cc=0;
ac=strlen(a);
bc=strlen(b);
add();
aa[j]=new char[cc+1];
strcpy(aa[j],c);
mystrrev(aa[j]);
strcpy(a,b);
strcpy(b,c);
}

while(cin>>s1>>s2)
{
if(strcmp(s1,"0")==0 && strcmp(s2,"0")==0) break;
//if(strlen(s1)>strlen(s2) || (strlen(s1)==strlen(s2) && strcmp(s1,s2)>0)) {strcpy(s3,s1);strcpy(s1,s2);strcpy(s2,s3);}
mys=0;
for(int i=2;i<=500;i++)
{
//cout<<s1<<" "<<aa[i]<<" "<<s2<<" "<<(int)(strlen(aa[i])>=strlen(s1) && strcmp(aa[i],s1)>=0)<<" "<<(int)(strlen(aa[i])<strlen(s2) || (strlen(aa[i])==strlen(s2) && strcmp(s2,aa[i])>=0))<<"\n";
if(strlen(aa[i])>=strlen(s1) && strcmp(aa[i],s1)>=0 && ((strlen(aa[i])<strlen(s2) || (strlen(aa[i])==strlen(s2) && strcmp(s2,aa[i])>=0)))) mys++;
if(strlen(aa[i])>strlen(s2)) break;
}
cout<<mys<<"\n";

//for(j=strlen(aa[n])-1;j>=0;j--) cout<<aa[n][j];
//cout<<"\n";
}

return 1;
}
[/cpp]

Thanx in advance.....
...I was born to code...

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Thu Jan 22, 2004 7:52 am

try this :

Code: Select all

1 1
1 2
0 0
output:

Code: Select all

1
2
gut lak :)
Kalo mau kaya, buat apa sekolah?

aakash_mandhar
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore

Post by aakash_mandhar » Sat Jan 24, 2004 10:19 am

I found the mistake and corrected it.. Thanks anyways :)
...I was born to code...

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

10183

Post by lovemagic » Fri Sep 10, 2004 10:15 pm

i try a lot but i can't understand why my code is wrong.
e.g. i generate first 500 fibs & do a normal search
khobaib

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Fri Sep 10, 2004 10:31 pm

Hi!! lovemagic this I/O is from my AC code
Input :

Code: Select all

10 100
100 1000
5000 9000
1234000 123456000
5567 900000000
34556 10000000000000
43324234 85675676576575675675
8678678 345345345345345345353453453
235432435425 4364364653453646353643645656345646345
1 100000000000000000000000
234134 454765765674567457645
123421341234234 3465546345465634546564636 
453643644654656645 45645465645465564645465654465465645
1 2
1 5
5 5
6 7
4 5
1 1
334 45564645
4356 56765878768787678768657856785576
23545 6547657457665
234535 46765758908765432
12 500000000000
45 9000000000000000000000000000000000
2354 566546456456456746545765464564
0 0
Ouput:

Code: Select all

5
5
1
10
25
40
59
94
120
110
73
50
81
2
4
1
0
1
1
25
134
40
54
51
155
127

Hope its Helps :)
Keep posting!!

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

Post by lovemagic » Sun Sep 12, 2004 9:43 pm

Thanks.Ac now
khobaib

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

10183

Post by Eduard » Wed Sep 22, 2004 1:37 pm

I'm going crazy of thinking about this problem.
The problem is vary ease I thing,but I'm getting WA,WA,WA....
WHY???
Please somebody give me some tests please(Special cases if there are ).
Thanks.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Thu Sep 23, 2004 6:09 am

Hi Eduard here http://online-judge.uva.es/board/viewtopic.php?t=6392
some I/O did you test with that??? if you want more I can post here more I have many belive me jeje
Hope its Helps
Keep posting!! :)

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Thu Sep 23, 2004 1:50 pm

Ghust_omega I got this problem AC by C++,but can't got it AC by Pascal.
My program outputs right answers for http://online-judge.uva.es/board/viewtopic.php?t=6392 test.
If you can, give me some critical inputs to find my mistake in Pascal code.
Thanks.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Post Reply

Return to “Volume 101 (10100-10199)”