UVa 369

From Algorithmist
Jump to navigation Jump to search

Problem Number - Problem Name[edit]

369 - Combinations

Summary[edit]

You are required to evaluate which is equal to

Explanation[edit]

Consider the following example:



Cancel 94!



Cancel 96 with 2*6 = 8 and 99 with 3 = 33 and 100 with 4*5 = 5


Gotchas[edit]

You should cancel and simplify the formula as much as possible, to avoid overflow.

Notes[edit]

The result of will fit in a 32-bit int

Implementations[edit]

Using long int in storing the result should be enough.

Optimizations[edit]

Just Simplify the formula to fit in a 32-bit int.

Alternative solution[edit]

Generate Pascal's triangle by using addition and then just do a simple lookup for each of the queries. It's a simpler method which is also much faster.

Input[edit]

20 5
18 6
15 7
10 5
100 100
40 5
0  0

Output[edit]

20 things taken 5 at a time is 15504 exactly.
18 things taken 6 at a time is 18564 exactly.
15 things taken 7 at a time is 6435 exactly.
10 things taken 5 at a time is 252 exactly.
100 things taken 100 at a time is 1 exactly.
40 things taken 5 at a time is 658008 exactly.

Solutions[edit]

References[edit]

  1. http://icpcres.ecs.baylor.edu/onlinejudge/external/3/369.html
  2. http://en.wikipedia.org/wiki/Combination
  3. http://online-judge.uva.es/board/viewtopic.php?f=4&t=9463&p=40846&hilit=369

Hussein Al Sayed 04:11, 28 August 2008 (UTC) http://www.algorithmist.com/index.php/Category:Math