10219 - Find the ways !

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10219 - Find the ways !

Post by prom » Sun Aug 18, 2002 1:10 am

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

Post by wyvmak » Sun Sep 01, 2002 10:09 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

Post by mido » Thu Sep 18, 2003 4:19 pm

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

Post by mido » Mon Sep 22, 2003 9:58 am

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

Post by Andrew Neitsch » Tue Jul 20, 2004 8:52 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

Post by oulongbin » Mon Jul 26, 2004 1:59 pm

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

Post by Andrew Neitsch » Mon Jul 26, 2004 11:31 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

Post by oulongbin » Wed Jul 28, 2004 8:26 am

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

Andrew Neitsch
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm

Post by Andrew Neitsch » Wed Jul 28, 2004 6:20 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
Location: buet, dhaka, bangladesh

10219

Post by ayon » Thu Nov 24, 2005 9:04 pm

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
Location: Dhaka, Bangladesh
Contact:

Re: WA 10219 find the ways!

Post by Solaris » Fri Nov 25, 2005 10:22 am

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

Post by yogeshgo05 » Fri Feb 17, 2006 12:17 pm

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:

Post by mf » Fri Feb 17, 2006 2:46 pm

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

Post by yogeshgo05 » Fri Feb 17, 2006 3:56 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:

Post by mf » Fri Feb 17, 2006 4:50 pm

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

Post Reply

Return to “Volume 102 (10200-10299)”