## 10219 - Find the ways !

Moderator: Board moderators

prom
New poster
Posts: 10
Joined: Thu Jul 25, 2002 11:58 pm
Location: Poland

### 10219 - Find the ways !

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
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
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
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

### 10219 help

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
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt
Found the bug..(very special case if you like to know)

Andrew Neitsch
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm
Don't do ceil(); do floor()+1. E.g. 100 has 3 digits.

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

### 10219

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
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm
The binomial coefficients will be sufficiently large that they will not fit in an integer, though the number of digits will.

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China
Sorry,i am not very know what is your meaning.
Could you explain it more particular?
Thanks.

Andrew Neitsch
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm
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
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm

### 10219

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
``````
Last edited by ayon on Fri Nov 25, 2005 12:24 pm, edited 1 time in total.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:

### Re: WA 10219 find the ways!

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 ..
Where's the "Any" key?

yogeshgo05
New poster
Posts: 47
Joined: Sun Nov 27, 2005 12:43 pm

### 10219 compile errro strange

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
New poster
Posts: 47
Joined: Sun Nov 27, 2005 12:43 pm
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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
It seems that fcvt() is also missing at UVa.