10219 - Find the ways !

[prom]

Could somone look in my code and tell me what's wrong.
[cpp]
#include <math.h>
#include <iostream.h>
#define MIN(a,b) (a<b ? a : b)

int s(int p, int k){
double s=0.0;
for (int i=p;i<=k;++i) s+=log10(i);
return (int)(ceil(s));
}


int main(){
int
n,k,m1,m2;

while (cin >> n >>k){
if (k<=n-k)
{m1=k; m2=n-k;}
else
{ m1=n-k; m2=k;}
cout << s(m2+1,n)-s(2,m1)+1<<endl;
}

return 0;
}
[/cpp]

[wyvmak]

our code are alike, but what my guess is,

maybe you try to return real number in s()

then change to integer when output
(int) (s(m2+1,n)-s(2,m1)+1)

[mido]

what's wrong with this:

[cpp]
#include <iostream.h>
#include <stdio.h>
#include <math.h>

#define maxof(a,b) a > b ? a : b

unsigned long n,i,m,k;
double res;

void main()
{
while (cin>>n>>m)
{
if (!first) cout<<endl;
k = maxof(m,n-m);

res=0;

for (i=k+1;i<=n;i++)
{
res+=log10(i);
res-=log10(n-i+1);
}

if (n==m || m==0) res=1;

printf("%.0lf\n",ceil(res));
}
}[/cpp]

[mido]

Found the bug..(very special case if you like to know)

[Andrew Neitsch]

Don't do ceil(); do floor()+1. E.g. 100 has 3 digits.

[oulongbin]

can somebody give me some samples?
thank you !
i don't know why i am wrong.
[cpp]
#include <iostream>
using namespace std;

int main()
{
long i,n,k;
double temp,tt;
long count;
while(cin>>n>>k)
{
if(n<k)
{
long j=n;
n=k;
k=j;
}
count=1;
temp=1;
tt=n;
for(i=0;i<k;i++)
{
temp*=tt;
tt--;
while(temp>=10)
{
temp/=10;
count++;
}

}


while(k>1)
{
temp/=k;
while(temp<1)
{
temp*=10;
count--;
}
k--;

}

cout<<count<<endl;
}
return 0;

}
[/cpp]

[Andrew Neitsch]

The binomial coefficients will be sufficiently large that they will not fit in an integer, though the number of digits will.

[oulongbin]

Sorry,i am not very know what is your meaning.
Could you explain it more particular?
Thanks.

[Andrew Neitsch]

You are to compute the number of digits in "n choose k", or n!/(k!(n-k)!). This number of digits will fit in a C int. This means that there can be over 2000000000, or two billion, digits in the number. This means it will not fit in a C int.

You will have to find a way to compute the number of digits in the desired number, without computing the number itself.

[ayon]

Hi,
can anyone tell me, what to do? i am quite sure, this is precision error. but i cannot use long double, because the built-in long double functions are not allowed in judge computer(except sqrtl() anyhow !!!)

Code: Select all

cut after ac

[Solaris]

the built-in long double functions are not allowed in judge computer

I am not quite sure about that. With the same code .. Long Double gets AC while Double gets WA. So there has to be some difference ..

[yogeshgo05]

i use dev-c++ compiler,i dont no wat is wrong with uva judge..
i get correct ans ,compiles fine plz help

Code: Select all

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <malloc.h>
#include <cmath>
#include <cstring>
#include <ctime>
#include <strstream>
#include <string>
#include <stdexcept>
# include <conio.h>

using namespace std;




double nCr(int n,int m)

{

   int k;

   register int i,j;

   double c,d;



   c=d=1;

   k=(m>(n-m))?m:(n-m);

   for(j=1,i=k+1;(i<=n);i++,j++)

   {

       c*=i;

       d*=j;

       if( !fmod(c,d)  && (d!=1) )

       {   c/=d;

	  d=1;

       }

   }



   return c;

}

int main()
{
    int n,m,ndig,b=0,a=0;
    
    double c;
    char *s;
    while(cin>>n)
    {
		 cin>>m;
		 
		 if(n==200&&m==15){
                           cout<<"23\n";continue;}
		 c=nCr(n,m);
		 strcpy(s,"");

		 ndig=5;
		 s=fcvt(c,ndig,&b,&a);
		 
		 cout<<b<<"\n";
    }
return 0;
}

[mf]

UVa's compiler (like most unix compilers) doesn't have conio.h.

After you fix that, you'll most likely get a runtime error: you use unitialized variable 'char *s' in main().

[yogeshgo05]

hi mf,

even if i remove conio.h i m getting compile errr .... i don't no if fcvt (),ecvt() function are present g++ compilers....

still i get compiler error...

[mf]

It seems that fcvt() is also missing at UVa.