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;
}

Comments

Popular posts from this blog

SPOJ-CMG - Collecting Mango

LightOJ 1009 - Back to Underworld

LeetCode Palindrome Number