Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

StrawberryInsha2k's blog

By StrawberryInsha2k, history, 2 months ago, In English,

Given C identical charities and N unique coins, find the number of ways of distributing the N coins to the C charities such that each charity gets at least 1, 2 or 3 coins based on input. [For a test case, this number M (1, 2 or 3) is fixed.]

T N C M

Sample Input:

3 5 3 1 5 2 2 6 2 3

Sample Output:

25 10 10

I defined dp[i][j] as the number of ways of distributing i coins to j charities. Then, a recursion relation should be derived in each of these three cases:

So for 1 at least 1 coin dp[i][j]=j∗dp[i−1][j]+dp[i−1][j−1]

I am unable to figure out the recurrence relation for at least 2 coins and at least 3 coins. Can you please explain the other two recurrence relation by clearly defining each states and transitions. I would be highly obliged to you and much of time will be saved.

Thank You

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Sample Input ( T followed by N C M where N is the total number of unique coins and C is the number of identical charities and M is the number of coins each charity at least gets (it is either 1, 2 , 3). Sample Input : 3

5 3 1

5 2 2

6 2 3 Sample Output : 25 10 10