Marbles

April 27, 2009 at 8:03 am 1 comment

This one is good if you want to remember basic Permutations and Combinations from class XI and XII

http://www.codechef.com/problems/MARBLES/

Advertisements

Entry filed under: Uncategorized.

The Next Palindrome Byteland

1 Comment Add your own

  • 1. narinderberi  |  April 27, 2009 at 8:06 am

    One you figure out the basic the rest is to multiply and divide big numbers.

    And the basic is very well explained at http://en.wikipedia.org/wiki/Combination in the section “Number of combinations with repetition”. I really liked the Example 2 explanation.

    After that it is just a simple program. The trick is that the question says the answer will fit in 64 bits for sure, so use a tricky way to multiply.

    using namespace std;

    void marbles()
    {
    int numTestCases;
    scanf(“%d”, &numTestCases);

    for(int iTestCase = 0; iTestCase < numTestCases; ++iTestCase)
    {
    int n, k;
    scanf(“%d %d”, &n, &k);

    if(n == k)
    {
    cout << 1 << endl;
    }
    else
    {
    n -= k;

    long long answer = 1;
    for(int i = n+1, j = 1; j <= k-1; i++, j++)
    {
    answer *= i;
    answer /= j;
    }

    cout << answer << endl;
    }
    }
    }

    int main()
    {
    marbles();
    return 0;
    }

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

Trackback this post  |  Subscribe to the comments via RSS Feed


Blog Stats

  • 4,036 hits

Recent Comments


%d bloggers like this: