UVa : 10219 (Find the ways !)


Title : Find the ways !

Link : http://uva.onlinejudge.org/external/102/10219.html

Tricky Lines :

  1. Each test case consists of one line containing two integers n (n>=1) and k (1<=<k=<n).
    // no limit mentioned for the value of n
  2. This number will always fit into an integer, i.e. it will be less than 2^31-1.
    // persuading you to use integer variable 😛

Analysis :

  1. u need to find the digits of nCk
    number_of_digits = floor ( log10 (number) ) + 1
  2. our output = floor ( log10 (nCk) ) + 1
    nCk = n! / (k! (n – k)!)
  3. n! = n * (n – 1) * (n – 2) * (n – 3) * …… * 1
    log10 (n!) = log10 (n) + log10 (n – 1) + log10 (n – 2) + …… + log10 (1)
  4. suppose, n = 10
    k = 7

    10C7

    nCk (10C7)

Runtime : 0.012s

Solution :

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define LL long long
using namespace std;

int main ()
{
    LL n, k;

    while ( cin >> n >> k ) {
        double digit = 0;

        if ( k > n - k ) {
            for ( LL i = k + 1; i <= n; i++ )
                digit += (log10 (i) - log10 (n - i + 1));
        }
        else {
            for ( LL i = n - k + 1; i <= n; i++ )
                digit += (log10 (i) - log10 (n - i + 1));
        }

        digit = floor (digit) + 1;

        printf ("%0.lf\n", digit);
    }

	return 0;
}

// @END_OF_SOURCE_CODE

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s