DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets Manager

Snippets has posted 5883 posts at DZone. View Full User Profile

A Solution For The "Binomial Showdown" Problem

04.13.2008

| 3726 views |

        A solution for the "Binomial Showdown" problem.

Problem description:
<a href="http://acm.uva.es/p/v5/530.html">http://acm.uva.es/p/v5/530.html</a>

Author: <a href="http://joanatrindade.wikidot.com">Joana Matos Fonseca da Trindade</a>
Date: 2008.04.11

/*
 * Solution for the "Binomial Showdown" problem.
 * UVa ID: 530
 */

#include <iostream>

using namespace std;

/* main */
int main() {
    int n, k;
    unsigned long long r; /* result */

    while(cin >> n >> k && ((n != 0) || (k != 0))) {
        /* init result */
        r = 1;

        /* if k is more than half of n, then use the complement */
        if(k > (n / 2)) {
            k = n - k;
        }

        /*         
         * C(n,k) = n! / (k!(n-k)!) =
         * (n)(n-1)(...)(n-k+1) / 2*3*4*(...)*k
         */ 
        for (int i=0; i<k; i++) {
            r = r * (n - i);   /* (n)(n-1)(...)(n-k+1) */
            r = r / (1 + i);   /* 2*3*4*(...)*k */
        }
        cout << r << endl;
    }
}

Tags: