Uva 530 - Binomial Showdown
/*
if n=10 and k=7 , then my program works as below:
mx = (n-k, k) = (3, 7) = 7;
mn = (n-k, k) = (3,7) = 3;
so, we got from the nCr formula like that : n! / r! * (n-r)! ;
so, 1*2*3*4*5*6*7*8*9*10 / 1*2*3*4*5*6*7*1*2*3 = 8*9*10 / 1*2*3;
that means multiplication of (n-k)+1 to n divided by multiplication of 1 to (n-k);
therefore, i=8,j=1,ans=1 and 8%1==0 so, ans=1; but ans%j!=0 when j=2 so, break, then ans=1*i=1*8=8;
i=9, j=2,ans=8 and 8%2==0 so, ans=4; but ans%j!=0 when j=3 so, break then ans=4*i=4*9=36;
i=10, j=3,ans=36 and ans%j==0 so, ans=12. finally ans=ans*i=12*10=120;
**** My Solution is 10C7=120;
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
LL n,k;
while(cin >> n >> k)
{
if(!n and !k) break;
LL ans=1,j=1,mx=max(n-k, k) , mn=min(n-k,k),i;
for(i=mx+1; i<=n; i++)
{
for(; j<=mn ; j++)
{
if(!( ans % j)) // i tried to minimize numerator as possible
{
ans /= j;
}
else
{
break;
}
}
ans*=i;
}
for(; j<=mn; j++)
{
ans/=j;
}
cout << ans << endl;
}
return 0;
}
if n=10 and k=7 , then my program works as below:
mx = (n-k, k) = (3, 7) = 7;
mn = (n-k, k) = (3,7) = 3;
so, we got from the nCr formula like that : n! / r! * (n-r)! ;
so, 1*2*3*4*5*6*7*8*9*10 / 1*2*3*4*5*6*7*1*2*3 = 8*9*10 / 1*2*3;
that means multiplication of (n-k)+1 to n divided by multiplication of 1 to (n-k);
therefore, i=8,j=1,ans=1 and 8%1==0 so, ans=1; but ans%j!=0 when j=2 so, break, then ans=1*i=1*8=8;
i=9, j=2,ans=8 and 8%2==0 so, ans=4; but ans%j!=0 when j=3 so, break then ans=4*i=4*9=36;
i=10, j=3,ans=36 and ans%j==0 so, ans=12. finally ans=ans*i=12*10=120;
**** My Solution is 10C7=120;
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
LL n,k;
while(cin >> n >> k)
{
if(!n and !k) break;
LL ans=1,j=1,mx=max(n-k, k) , mn=min(n-k,k),i;
for(i=mx+1; i<=n; i++)
{
for(; j<=mn ; j++)
{
if(!( ans % j)) // i tried to minimize numerator as possible
{
ans /= j;
}
else
{
break;
}
}
ans*=i;
}
for(; j<=mn; j++)
{
ans/=j;
}
cout << ans << endl;
}
return 0;
}
Comments
Post a Comment