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
Ghust_omega
Experienced poster
Posts: 115 Joined: Tue Apr 06, 2004 7:04 pmLocation: Venezuela
Post
by Ghust_omega Fri Sep 24, 2004 4:46 pm
Hi!!! Eduard how about this
Input:
Code: Select all
83 346930886
77 214636915
93 424238335
86 149760492
49 189641421
62 350490027
90 102520059
63 467513926
40 40383426
72 303455736
11 21595368
67 226956429
82 361021530
62 233665123
67 468703135
29 301979802
22 135723058
69 125898167
93 89018456
11 156478042
29 153377373
21 414544919
84 256898537
98 473594324
15 38664370
13 184803526
91 424268980
56 249241873
62 42999170
96 135497281
5 84420925
84 327336327
36 159126505
46 132621729
13 433925857
24 84353895
82 1100545
14 48233367
34 85990364
43 260313750
1 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0 0
ouput:
Code: Select all
32
31
31
30
32
32
29
33
29
32
30
31
32
31
33
34
32
30
28
34
32
35
31
32
30
35
31
31
28
29
35
32
31
31
37
31
20
31
31
32
474
Hope its Helps
Keep posting!!!
Eduard
Experienced poster
Posts: 183 Joined: Fri Sep 26, 2003 2:54 pmLocation: Armenia,Yerevan
Post
by Eduard Sat Sep 25, 2004 2:22 pm
Ghust_omega My program gives right answers to all of your tests.I think tere is just one good input that I can't find and that why got WA.
ica28
New poster
Posts: 1 Joined: Sat May 14, 2005 12:20 am
Post
by ica28 Sat May 14, 2005 12:41 am
this source is Compile Error on online judge
but this source run on my computer
Why Compile Error??
Code: Select all
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std ;
const int MAX = 101 ;
const int FIBMAX = 45 ;
const int STRFIBMAX = 407 ;
void Init( int* , string* ) ;
int GetCnt( string , string* ) ;
bool Fibs( string , string* ) ;
int main( void )
{
string Num[2] ;
string strFibs[STRFIBMAX] ;
int nFibs[FIBMAX] ;
Init( nFibs , strFibs ) ;
while( 1 )
{
cin >> Num[0] ;
cin >> Num[1] ;
if ( ( Num[0] == "0" ) && ( Num[1] == "0" ) )
break ;
cout << GetCnt( Num[1] , strFibs ) - GetCnt( Num[0] , strFibs )
+ ( Fibs( Num[0] , strFibs ) ? 1 : 0 ) << endl ;
}
return 0 ;
}
int GetCnt( string num , string* strFib )
{
int cnt = 0 ;
int i ;
for ( i = 0 ; i < STRFIBMAX ; i++ )
{
if( num.length() > strFib[i].length() )
{
cnt++ ;
}
else if( num.length() == strFib[i].length() )
{
if ( num >= strFib[i] )
cnt++ ;
}
}
return cnt ;
}
bool Fibs( string num , string* strFib )
{
int i ;
for ( i = 0 ; i < STRFIBMAX && strFib[i].length() <= num.length() ; i++ )
{
if ( num == strFib[i] )
return true ;
}
return false ;
}
void Init( int* nFib , string* strFib)
{
int i = 2 , j ;
int carry = 0 ;
nFib[0] = 1 ;
nFib[1] = 2 ;
int len1, len2 ;
char* temp , *tp1 , *tp2 ;
char chtp[10] ;
int tpi ;
while( 1 )
{
nFib[i] = nFib[i-1] + nFib[i-2] ;
if ( nFib[i] < nFib[i-1] )
break ;
i++ ;
}
for ( i = 0 ; i < FIBMAX ; i++ )
{
itoa( nFib[i] , chtp , 10 ) ;
strFib[i] = chtp ;
}
i = FIBMAX ;
while ( strFib[i-1].length() < 101 )
{
len1 = strFib[i-1].length() ;
len2 = strFib[i-2].length() ;
temp = new char[ len1 + 1 ] ;
tp1 = new char[ len1 + 1 ] ;
tp2 = new char[ len2 + 1 ] ;
strcpy( tp1 , strFib[i-1].c_str() ) ;
strcpy( tp2 , strFib[i-2].c_str() ) ;
temp[len1] = '\0' ;
for ( j = 0 ; j < len2 ; j++ )
{
tpi = tp1[ len1 - j - 1 ] - '0' +
tp2[ len2 - j - 1 ] - '0' + carry ;
if ( tpi >= 10 )
{
carry = 1 ;
tpi -= 10 ;
}
else
carry = 0 ;
temp[len1 - j - 1 ] = tpi + '0' ;
}
if ( len1 > len2 )
{
tpi = tp1[0] - '0' + carry ;
if ( tpi > 9 )
{
carry = 1 ;
tpi -= 10 ;
}
temp[0] = tpi + '0' ;
}
if ( carry )
{
strFib[i] = '1' ;
strFib[i] = strFib[i] + temp ;
i++ ;
}
else
strFib[i++] = temp ;
delete [] temp ;
delete [] tp1 ;
delete [] tp2 ;
}
}
dumb dan
Learning poster
Posts: 67 Joined: Tue Aug 05, 2003 1:02 am
Post
by dumb dan Sat May 14, 2005 9:57 am
85: implicit declaration of function `int itoa(...)'
rmotome
New poster
Posts: 14 Joined: Mon Jan 10, 2005 12:20 pmLocation: Kitchener, Ontario, Canada
Post
by rmotome Fri Jul 15, 2005 2:01 pm
There is an error in problem 10183 (How many Fibs?) ..... F[2] is defined as 2 instead of 1; you must however use the information as given in order to get an AC.
vijay03
New poster
Posts: 33 Joined: Wed Sep 13, 2006 6:46 pm
Contact:
Post
by vijay03 Sat Dec 30, 2006 10:32 pm
Whats the algorithm for this problem?
Spykaj
New poster
Posts: 47 Joined: Sun May 21, 2006 12:13 pm
Post
by Spykaj Sat Dec 30, 2006 11:02 pm
Use something like lower_bound and upper_bound
u must search it binary.
vijay03
New poster
Posts: 33 Joined: Wed Sep 13, 2006 6:46 pm
Contact:
Post
by vijay03 Mon Jan 01, 2007 9:23 am
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?
mad
New poster
Posts: 3 Joined: Sun Jun 24, 2007 11:51 pm
Post
by mad Wed Jul 04, 2007 6:25 am
I'm not managing to count the fibonacci numbers in a write way. Can someone help me? I'm having large answers (much more than the right one).
Thank you in advance!
Code: Select all
#include <stdio.h>
#include <string.h>
#define MAXDIGITS 101
typedef struct
{
char digits[MAXDIGITS];
int signbit;
int lastdigit;
} Bigint;
char *
sumbigint (char [], char []);
main ()
{
int quantfib; //quantity of fibonacci numbers in the interval
int num1;
int num2;
Bigint naux1;
Bigint naux2;
int i;
int j;
Bigint fibo[5000];
scanf ("%s %s\n", &naux1.digits, &naux2.digits);
while (strcmp (naux1.digits, "0") || strcmp (naux2.digits, "0"))
{
quantfib = 0;
strcpy (fibo[0].digits, "1");
strcpy (fibo[1].digits, "2");
//completing the array of fibonacci numbers
for (i = 2; i < 5000; i++)
strcpy (fibo[i].digits, sumbigint (fibo[i - 1].digits, fibo[i - 2].digits));
//counting the numbers of fibonacci numbers in the interval
for (i = 0; i < 5000; i++)
{
if ((strlen (fibo[i].digits) > strlen (naux1.digits)) && (strlen (fibo[i].digits) < strlen (naux2.digits)))
quantfib++;
else if ((strlen (fibo[i].digits) == strlen (naux1.digits)) && (strlen (fibo[i].digits) == strlen (naux2.digits)))
if ((strcmp (fibo[i].digits, naux1.digits) >= 0) && (strcmp (fibo[i].digits, naux2.digits) <= 0))
quantfib++;
else if ((strlen (fibo[i].digits) == strlen (naux1.digits)) && (strlen (fibo[i].digits) < strlen (naux2.digits)))
if (strcmp (fibo[i].digits, naux1.digits) >= 0)
quantfib++;
else if ((strlen (fibo[i].digits) > strlen (naux1.digits)) && (strlen (fibo[i].digits) == strlen (naux2.digits)))
if (strcmp (fibo[i].digits, naux2.digits) <= 0)
quantfib++;
}
printf ("%d\n", quantfib);
scanf ("%s %s\n", &naux1.digits, &naux2.digits);
}
}
char *
sumbigint (char str1[], char str2[])
{
int i; //always associated with str1
int j; //always associated with str2
int psum; //indicates the current position of the sum of the bigints
int carry;
char *sum;//result of the sum
int vsum;//value of a temporary sum
int tammaj;//the size of the biggest number
int temp;
int tmin;//the size of the lowest number
if (strlen(str1) >= strlen(str2))
{
tammaj = strlen(str1);
tmin = strlen(str2);
i = tammaj - 1;
j = tmin - 1;
}
else
{
tammaj = strlen(str2);
tmin = strlen(str1);
i = tmin - 1;
j = tammaj - 1;
}
carry = 0;
//more two characters (one for '\0' and another for one possible carry
sum = malloc (sizeof (char) * (tammaj + 2));
psum = 0;
do
{
//making the sum from right to left
vsum = (str1[i] - '0') + (str2[j] - '0') + carry;
if (vsum > 9)
carry = 1;
else
carry = 0;
sum[psum] = (vsum % 10) + '0';
i--;
j--;
psum++;
} while ((i >= 0) && (j >= 0));
//completing the sum of bigints
if (strlen (str1) == tammaj)
while (psum < tammaj)
{
if (vsum > 9)
{
vsum = carry + (str1[i] - '0');
sum[psum] = (vsum % 10) + '0';
i--;
psum++;
}
else
{
sum[psum] = str1[i];
psum++;
}
}
else
while (psum < tammaj)
{
if (vsum > 9)
{
vsum = carry + (str2[j] - '0');
sum[psum] = (vsum % 10) + '0';
j--;
psum++;
}
else
{
sum[psum] = str2[j];
psum++;
}
}
if (vsum > 9)
{
sum[psum] = '1';
psum++;
tammaj++;
}
//reversing the result (the sum)
for (i = 0, j = tammaj - 1; i < j; i++, j--)
{
temp = sum[i];
sum[i] = sum[j];
sum[j] = temp;
}
sum[psum] = '\0';
return sum;
}
armansuleimenov
New poster
Posts: 15 Joined: Tue Sep 25, 2007 3:07 amLocation: Astana, Kazakhstan
Contact:
Post
by armansuleimenov Tue Sep 25, 2007 3:20 am
I'm using BigInteger class (
http://online-judge.uva.es/board/viewto ... shed+suman ).
I've run my program with all the tests from the board, it solves all the tests correctly. But I'm getting Runtime Error from judge. What is the reason of RE? How to debug my program to find the reason (debugging using OJ will help me with other problems too:))?
Here is my code:
Code: Select all
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <strstream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
using namespace std;
namespace BigMath
{
............... see the link above
}
using namespace BigMath;
int main ()
{
//ifstream fin("p.in");
BigInteger fibo[510];
DATATYPE i;
i=1;
BigInteger& a=*new BigInteger(i);
BigInteger& b=*new BigInteger(i);
BigInteger& c=*new BigInteger(i);
fibo[2]=b;
for(i=3;i<=500;++i)
{
c=a+b;
a=b;
b=c;
fibo[i]=b;
}
cin >> a >> b;
while(!(a.isZero()&&b.isZero()))
{
int cnt=0;
for(i=2;i<=500;++i)
{
if(fibo[i]>=a && fibo[i]<=b)
cnt++;
if(fibo[i]>b)break;
}
cout<<cnt<<endl;
cin >> a >> b;
}
return 0;
}
mrunmoy
New poster
Posts: 17 Joined: Mon Apr 09, 2007 3:11 pmLocation: India
Contact:
Post
by mrunmoy Fri Dec 28, 2007 11:41 pm
Hi,
I have run through all the available test cases posted here related to problem number <10183> still i get WA.
6140898 How Many Fibs? Wrong answer C++ 0.010 2007-12-28 20:37:44
can anyone suggest some more test cases plz?
Here goes my code:-
Code: Select all
/* @JUDGE_ID: 59960OQ 10183 C "Brute Force" */
/* Solution to ACM UVa Problem 10183 - How many Fibs? */
/* Author- Mrunmoy Samal*/
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <time.h>
#define EQ 0
#define GT 1
#define LT -1
#define MAX_SIZE 484
#define MAX_COL 102
char result[MAX_COL];
char sum[MAX_COL];
char prev[MAX_COL];
struct struct_tag
{
char LookUp[MAX_SIZE][MAX_COL];
}LookUpTable;
char a_fib[MAX_COL] =
"1000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000";
char b_fib[MAX_COL] =
"1000000000000000000000000000000000000000000000000000\
0000000000000000000000000000000000000000000000000";
int firsttime = 1;
int add(void);
int compareBigInteger(int k,char ch);
int main()
{
int fib; // 0 <= n <= 5000
int i,j,count,eqA,eqB,done,found;
char *ptrSrc,*ptrTgt,*ptrTgt2;
/*clock_t start = clock();*/
fib = 483;
result[0] = '1';
result[1] = '\0';
for(i=0;i<=fib;i++)
{
add(); // sum = result + prev
ptrSrc = result;ptrTgt = prev;
while(*ptrTgt++=*ptrSrc++); // prev = result
ptrSrc = sum;ptrTgt = result;
ptrTgt2 = LookUpTable.LookUp[i];
while(*ptrTgt2++=*ptrTgt++=*ptrSrc++); // result = sum, fib(i) = sum
}
done=0;
firsttime=1;
while(!done)
{
count = 0;
scanf("%s %s",&a_fib,&b_fib);
if((a_fib[0] =='0') && (b_fib[0]=='0'))
{
done=1;
}
else
{
if(compareBigInteger(0,'c')==EQ)
{
found = 0;
i=2;
while(i<=fib)
{
eqA = compareBigInteger(i,'a');
if(eqA==EQ)
{
found = 1;
i = MAX_SIZE;
}
else
{
i++;
}
}
if(found)count=1;
}
else
{
i=2;
while(i<=fib)
{
eqA = compareBigInteger(i,'a');
if(eqA==LT)
{
i++;
}
else
{
j = i;
i=MAX_SIZE;
count=1;
}
}
while(j<=fib)
{
eqB = compareBigInteger(j,'b');
if(eqB==LT)
{
j++;
count++;
}
else
{
if(eqB==GT)
{
j--;
count--;
}
j=MAX_SIZE;
}
}
}
if(firsttime)
{
printf("%d",count);
firsttime=0;
}
else
{
printf("\n%d",count);
}
}
}
/* Code you want timed here */
/*printf("Time elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);*/
return 0;
}
int add(void)
{
int a;
int b;
int tot,u,carry;
int i,j,k,len1;
if(firsttime)
{
sum[0] = '0';
sum[1] = '\0';
firsttime=0;
return 0;
}
i = strlen(result) - 1;
j = strlen(prev) - 1;
k = 0;
carry =0;
while(i >= 0)
{
a = result[i] - '0';
if(j >= 0)
{
b = prev[j] - '0';
j--;
}
else
{
b = 0;
}
tot = a + b + carry;
if(tot>=10)
{
u = tot%10;
carry = tot/10;
sum[k] = u + '0';
sum[k+1] = carry + '0';
}
else
{
sum[k] = tot + '0';
carry = 0;
}
k++;
i--;
}
sum[k+carry] ='\0';
len1 = strlen(sum) - 1;
for(k=0;k<=len1/2;k++)
{
a = sum[k];
sum[k] = sum[len1-k];
sum[len1-k] = a;
}
return 1;
}
/*
Returns 1 if Lookup[i] > val
-1 if Lookup[i] < val
0 if equal
*/
int compareBigInteger(int k,char ch)
{
int len1;
int len2;
int i,there_is_a_match,retval=0;
char *ptr1,*ptr2;
len1 = strlen(LookUpTable.LookUp[k]);
if(ch =='a')
{
len1 = strlen(LookUpTable.LookUp[k]);
len2 = strlen(a_fib);
ptr1 = LookUpTable.LookUp[k];
ptr2 = a_fib;
}
else if(ch=='b')
{
len1 = strlen(LookUpTable.LookUp[k]);
len2 = strlen(b_fib);
ptr1 = LookUpTable.LookUp[k];
ptr2 = b_fib;
}
else
{
len1 = strlen(a_fib);
len2 = strlen(b_fib);
ptr1 = a_fib;
ptr2 = b_fib;
}
if(len1>len2) // value is > than lookuptable value
{
retval = GT;
}
else if(len1==len2) // the lengths are equal
{
// now compare the first digit of both if the first digit is same
// then compare the next digit, which tells us if
// the BigInteger_curr_row[k] is greater than ten_raised_to_60
i = 0;
there_is_a_match = 1;
retval = 0;
while(there_is_a_match && (i<len1))
{
if( (ptr1[i] == ptr2[i]) && (retval==EQ) )
{
retval = EQ; // number is equal so we reach last row
i++; // continue comparing
}
else
{
if(ptr1[i] > ptr2[i])
{
there_is_a_match = 0; // number is greater so we reach last row
retval = GT;
}
else
{
there_is_a_match = 0;
retval = LT; // number is smaller so continue
}
}
}
}
else
{
retval = LT;
}
return retval;
}[/code]
Best Regards,
mrunmoy
New poster
Posts: 17 Joined: Mon Apr 09, 2007 3:11 pmLocation: India
Contact:
Post
by mrunmoy Fri Dec 28, 2007 11:45 pm
here are the test cases which my code passes:-
10 100
Here is the output
5
Best Regards,
Sayeef
New poster
Posts: 12 Joined: Sun Jun 18, 2006 3:06 am
Post
by Sayeef Tue Jan 01, 2008 7:12 am
I keep Getting WA for this problem plz help
Code: Select all
#include<stdio.h>
#include<string.h>
#define MAX 1050
int cmp(char a[],char b[] )
{
int al,bl;
al=strlen(a);
bl=strlen(b);
if(al!=bl)
return al-bl;
for(int i=0;a[i];i++)
{
if(a[i]!=b[i])
return a[i]-b[i];
}
return 0;
}
void strev(char *a,int len)
{
int i,j;
char tmp;
j=len;
for(i=0,j=len-1;i<len/2;i++,j--)
{
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
}
class bigInt
{
public:
char *val;
void set_val(const char *c)
{
int len;
len=strlen(c);
val=new char[len+1];
strcpy(val,c);
}
};
bigInt fib[5001];
void add(char a[],char b[],bigInt &c)
{
int i,j,p,lena,lenb,ad=0;
char tc[MAX]={'\0'};
//strcpy(ta,a);
//strcpy(tb,b);
//strcpy(tc,c);
lena=strlen(a);
lenb=strlen(b);
strev(a,lena);
strev(b,lenb);
for(i=0,j=0,p=0;;p++)
{
if(a[i]=='\0'&&b[j]=='\0')
{
if(ad!=0)
tc[p]=ad+48;
int lenc=strlen(tc);
strev(tc,lenc);
c.set_val(tc);
return;
}
else if(a[i]=='\0')
{
ad=(b[j++]-'0') + ad;
tc[p]=ad%10+48;
ad=ad/10;
}
else if(b[j]=='\0')
{
ad=(a[i++]-'0') + ad;
tc[p]=ad%10+48;
ad=ad/10;
}
else
{
ad=(a[i++]-'0') + (b[j++]-'0')+ad;
tc[p]=ad%10+48;
ad=ad/10;
}
}
}
void fib_gen()
{
int i;
fib[0].set_val("0");
fib[1].set_val("1");
fib[2].set_val("2");
char ta[1050],tb[1050];
for(i=3;i<600;i++)
{
strcpy(ta,fib[i-1].val);
strcpy(tb,fib[i-2].val);
add(ta,tb,fib[i]);
}
}
int main()
{
fib_gen();
int n;
char a[150]={"\0"},b[150]={'\0'};
while(scanf("%s %s",a,b)&&(strcmp(a,"0")||strcmp(b,"0")))
{
int i=0,s_loc=0,p,fl=0;
while(cmp(fib[i].val,a)<0)
i++;
s_loc=i;
i=0;
while(cmp(fib[i].val,b)<=0)
i++;
printf("%d\n",i-s_loc);
}
return 0;
}
zyxw
New poster
Posts: 24 Joined: Sat Mar 22, 2008 5:49 amLocation: Chennai
Contact:
Post
by zyxw Thu May 29, 2008 8:15 am
To mrunmoy...
for this input:
Code: Select all
1 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
my AC code prints:
I am not totally useless, because I can still be used as a bad example
