Algorithm
problem link- https://www.spoj.com/problems/MAY99_4/
MAY99_4 - Rachu
Rachu is very happy today because its his birthday :D and he has a birthday party at home with 'r' friends.
He went to market to purchase something to eat. (He is really fond of eating :P ). At the shop he found muffins at a very reasonable price (ohh!! he loves muffins ;) ). He bought 'n' muffins from the shop.
After reaching home he is wondering that in how many ways he can distribute these muffins between his friends.
He shouldn't be rash so he would give at least 1 muffin to each friend. For rest of the muffins left he can distribute it in any manner. He is still wondering the no. of ways in which he can distribute these muffins.
Help him out by writing a code which calculates the number of ways the muffins could be distributed and print "-1" (quotes for clarity) if its impossible for him to distribute the muffins.
Consider each muffin as similar. The number of ways could go very large so output the result after taking a mod with 10000007.
Input
The input consists of 2 integers: n - the number of muffins, and r - The number of friends
Output
The required answer modulo 10000007.
Constraints
1 <= n, r <= 100
Example
Input: 2 1 Output: 1
Input: 4 2 Output: 3
Explanation
In 1st case he has 2 muffins and called only 1 friend so he gave both the muffins to him.
In 2nd case he 1st give 1 muffin each to both. Then he can give 0 muffin to 1st friend and 2 to the 2nd or 1 muffin to each or 2 muffins to 1st friend and 0 to the 2nd.
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
n, k = map(int, raw_input().split())
if n < k:
print(-1)
exit(0)
n, k = n - 1, k - 1
dp = [[0 for i in range(500)] for j in range(500)]
for i in range(n + 5):
for j in range(i + 1):
if j == 0:
dp[i][j] = 1
else:
dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % 10000007
print(dp[n][k])Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 10000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
const int MAXN = 1e5+5;
int n, r;
int dp[105][105];
int solve(int idx, int left){
if(left < 0) return 0;
if(left == 0) return 1;
if(idx >= r) return 0;
if(dp[idx][left] != -1) return dp[idx][left];
int res = 0;
for(int i = 0; i <= left; i++){
res += solve(idx + 1, left - i);
res %= MOD;
}
return dp[idx][left] = res;
}
int main(){
io;
memset(dp, -1, sizeof dp);
cin >> n >> r;
if(r > n)
cout << -1 << endl;
else{
n -= r;
cout << solve(0, n) << endl;
}
return 0;
}Input
Output
Demonstration
SPOJ Solution-Rachu -Solution in C, C++, Java, Python