Page 1 of 3
10219 - Find the ways !
Posted: Sun Aug 18, 2002 1:10 am
by 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]
Posted: Sun Sep 01, 2002 10:09 am
by 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)
10219 help
Posted: Thu Sep 18, 2003 4:19 pm
by 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]
Posted: Mon Sep 22, 2003 9:58 am
by mido
Found the bug..(very special case if you like to know)
Posted: Tue Jul 20, 2004 8:52 pm
by Andrew Neitsch
Don't do ceil(); do floor()+1. E.g. 100 has 3 digits.
10219
Posted: Mon Jul 26, 2004 1:59 pm
by 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]
Posted: Mon Jul 26, 2004 11:31 pm
by Andrew Neitsch
The binomial coefficients will be sufficiently large that they will not fit in an integer, though the number of digits will.
Posted: Wed Jul 28, 2004 8:26 am
by oulongbin
Sorry,i am not very know what is your meaning.
Could you explain it more particular?
Thanks.
Posted: Wed Jul 28, 2004 6:20 pm
by 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.
10219
Posted: Thu Nov 24, 2005 9:04 pm
by 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 !!!)
Re: WA 10219 find the ways!
Posted: Fri Nov 25, 2005 10:22 am
by Solaris
ayon wrote:
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 ..
10219 compile errro strange
Posted: Fri Feb 17, 2006 12:17 pm
by 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;
}
Posted: Fri Feb 17, 2006 2:46 pm
by 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().
Posted: Fri Feb 17, 2006 3:56 pm
by 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...
Posted: Fri Feb 17, 2006 4:50 pm
by mf
It seems that fcvt() is also missing at UVa.