# UVa 10910

Jump to navigation
Jump to search

## 10910 - Marks Distribution[edit]

## Summary[edit]

A Dynamic Programming counting problem. Solve the problem by counting it with its subproblems. This is an implicit solution. There is also another explicit solution which gives a direct formula.

## Explanation[edit]

- can be defined recursively
- and which basically just states that the number of ways we can have
**N**objects that sum up to**T**and up to minimum**P**is just the summation of the number of ways that having the number**i**as the current number, and the subproblem of**N-1**objects that sums up to**T-i**, still with a minimum**P**.

- Alternate Solution
- First, for getting a pass mark in all the N subjects, put 'P' for all the subjects. Now, the number of ways for the rest of the marks to be distributed in 'N' subjects is the number of integrals solutions of . So, finally the answer reduces to

## Optimizations[edit]

Memoization is fine, and this problem can be solved bottom-up.

## Input[edit]

3 3 34 10 3 34 10 7 50 2

## Output[edit]

15 15 5245786