# UVa 369

Jump to navigation
Jump to search

## Contents

## Problem Number - Problem Name[edit]

## 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]

- http://icpcres.ecs.baylor.edu/onlinejudge/external/3/369.html
- http://en.wikipedia.org/wiki/Combination
- 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