## Marbles

*April 27, 2009 at 8:03 am* *narinderberi* *
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.

1.narinderberi | April 27, 2009 at 8:06 amOne 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;

}