Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Dish Distribution CodeChef Solution
Problem -Dish Distribution CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Dish Distribution CodeChef Solution in C++17
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rangeC(i, start, end) for (i = start; i < end; i++)
#define range(i, end) rangeC(i, 0, end)
#define MOD 1000000007
int solve()
{
ll n, m, i, j, k;
cin >> n >> m;
int xi[m + 1], yi[m + 1];
ll dp[m + 1][n + 1];
range(i, m)
{
ll x, y;
cin >> x >> y;
xi[i + 1] = x;
yi[i + 1] = y;
}
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i <= m; i++)
{
for (int j = xi[i]; j <= yi[i]; j++)
{
for (int d = j; d <= n; d++)
{
dp[i][d] += dp[i - 1][d - j];
dp[i][d] %= MOD;
}
}
}
cout << dp[m][n] << endl;
return 0;
}
int main()
{
// std::ifstream in("i&o/input.txt");
// std::streambuf *cinbuf = std::cin.rdbuf();
// std::cin.rdbuf(in.rdbuf());
// std::ofstream out("i&o/output.txt");
// std::streambuf *coutbuf = std::cout.rdbuf();
// std::cout.rdbuf(out.rdbuf());
ll t;
cin >> t;
for (; t; t--)
solve();
return 0;
}Dish Distribution CodeChef Solution in C++14
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mod (int (1e9 + 7))
#define rep(i,a,b) for(int i = a; i < b; i++)
const int N = 1e6 + 7;
int helper(vector<pair<ll, ll>>& chef, int index, vector<vector<int>>& dp, int dishes) {
if(index >= chef.size()) {
if(dishes == 0) return 1;
return 0;
}
if(dp[index][dishes] != -1) return dp[index][dishes];
ll ans = 0;
for(int i = chef[index].first; i <= chef[index].second; i++) {
if(dishes >= i) ans = (ans + helper(chef, index + 1, dp, dishes - i)) % mod;
else break;
}
return dp[index][dishes] = ans;
}
int solve() {
int n, m;
cin >> n >> m;
vector<pair<ll, ll>> chef(m);
vector<vector<int>> dp(m + 10, vector<int>(n + 10, -1));
rep(i,0,m) {
int x, y;
cin >> x >> y;
chef[i] = {x, y};
}
return helper(chef, 0, dp, n);
}
int main() {
int t;
cin >> t;
while(t--) cout << solve() << endl;
return 0;
}Dish Distribution CodeChef Solution in PYTH 3
def generate_sums(array):
cur_sum = 0
sums = [0] * len(array)
for i in range(len(array)):
cur_sum += array[i]
sums[i] = cur_sum
return sums
def dishdis(foods, cooks):
cook = cooks.pop()
previous = [1 if cook[0] <= food_count <= cook[1] else 0 for food_count in range(foods + 1)]
previous_sums = generate_sums(previous)
while cooks:
cook = cooks.pop()
current = [0] * (foods + 1)
for i in range(0, foods + 1):
interval_start = max(-1, i - cook[1] - 1)
interval_end = i - cook[0]
if interval_end < 0:
current[i] = 0
elif interval_start < 0:
current[i] = previous_sums[interval_end]
else:
current[i] = previous_sums[interval_end] - previous_sums[interval_start]
current[i] %= 1000000007
previous = current
previous_sums = generate_sums(previous)
return previous[foods]
if __name__ == '__main__':
for _ in range(int(input())):
foods, cook_count = [int(x) for x in input().split()]
cooks = [[int(x) for x in input().split()] for _ in range(cook_count)]
print(dishdis(foods, cooks))Dish Distribution CodeChef Solution in C
#include<stdio.h>
#include<stdlib.h>
#define mod 1000000007
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d %d",&n,&m);
int x,y;
int a[101];
for(int i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
a[i]=y-x;
n-=x;
}
if(n>=0)
{
int matrix[101][101]={0};
matrix[0][0]=1;
for(int i=1;i<=m;i++)
{
for(int j=0;j<=n;j++)
{
for(int k=0;k<=a[i];k++)
{
if(j-k>=0)
{
matrix[i][j]=(matrix[i][j]+matrix[i-1][j-k])%mod;
}
}
}
}
printf("%d\n",matrix[m][n]);
}
else
{
printf("0");
}
}
return 0;
}
Dish Distribution CodeChef Solution in JAVA
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static long computeNoOfWays(int cooks[][], int m, int n) {
long dp[][] = new long[m + 1][n + 1];
for(int i = 0; i <= m; i++) {
for(int j = 0; j <= n; j++) {
if(i == 0 && j == 0)
dp[i][j] = 1;
else if(i == 0) {
dp[i][j] = 0;
}
else {
for(int k = cooks[i - 1][0]; k <= cooks[i - 1][1]; k++) {
if(j >= k) {
dp[i][j] = (dp[i][j] % 1000000007 + dp[i - 1][j - k] % 1000000007) % 1000000007;
}
else {
break;
}
}
}
}
}
return dp[m][n] % 1000000007;
}
public static void main (String[] args) throws java.lang.Exception
{
Scanner scn = new Scanner(System.in);
int t = Integer.parseInt(scn.nextLine());
long answers[] = new long[t];
for(int i = 0; i < t; i++) {
int n = Integer.parseInt(scn.next());
int m = Integer.parseInt(scn.next());
int cooks[][] = new int[m][2];
for(int j = 0; j < m; j++) {
cooks[j][0] = Integer.parseInt(scn.next());
cooks[j][1] = Integer.parseInt(scn.next());
}
answers[i] = computeNoOfWays(cooks, m, n);
}
for(int i = 0; i < t; i++) {
System.out.println(answers[i]);
}
}
}Dish Distribution CodeChef Solution in PYPY 3
# cook your dish here
def generate_sums(array):
cur_sum = 0
sums = [0] * len(array)
for i in range(len(array)):
cur_sum += array[i]
sums[i] = cur_sum
return sums
def dishdis(foods, cooks):
cook = cooks.pop()
previous = [1 if cook[0] <= food_count <= cook[1] else 0 for food_count in range(foods + 1)]
previous_sums = generate_sums(previous)
while cooks:
cook = cooks.pop()
current = [0] * (foods + 1)
for i in range(0, foods + 1):
interval_start = max(-1, i - cook[1] - 1)
interval_end = i - cook[0]
if interval_end < 0:
current[i] = 0
elif interval_start < 0:
current[i] = previous_sums[interval_end]
else:
current[i] = previous_sums[interval_end] - previous_sums[interval_start]
current[i] %= 1000000007
previous = current
previous_sums = generate_sums(previous)
return previous[foods]
if __name__ == '__main__':
for _ in range(int(input())):
foods, cook_count = [int(x) for x in input().split()]
cooks = [[int(x) for x in input().split()] for _ in range(cook_count)]
print(dishdis(foods, cooks))
Dish Distribution CodeChef Solution in PYTH
# cook your code here
# dish distribution - dishdis.py
#mod = 1007
mod = 1000000007
"""
Generating function:
need to find coefficient of x^n in
(1+x+..+x^m1)(1+x+..+x^m2)...(1+x+..x^mk)
= sum{j=0-inf, binom(k+j-1,j) x^j } * prod {i=1..k, (1-x^(mi+1)) }
"""
# polynomials are stored as lists of coefficients
# poly[0] = coef of x^0, poly[n] = coef of x^n
# polyMult assumes that both polys are lists with n+1 elements
def polyMult(p1, p2, n, mod):
answer = [0]*(n+1)
for k in range(n+1):
for i in range(k+1):
answer[k] = (answer[k] + p1[i] * p2[k-i]) % mod
return answer
# polyMult2 assumes that first poly is list with n+1 elements
# second poly is always 1+x+... +x^m
# so p2[i] = 1 if i<=m, 0 if i>m
def polyMult2(p1, m, n, mod):
answer = [0]*(n+1)
if m>n:
m = n
for k in range(n+1):
for i in range(min(k+1,m+1)):
answer[k] = (answer[k] + p1[k-i]) % mod
return answer
"""
Still too long.
New plan:
multiply out (1-x^y_i) 0<=i<m
keeping terms up to x^n
multiply this by:
combin(k+j-1,j) x^j j=0..n
Need new polynomial format to avoid big loops through
zeros. poly = [ [c_i,k_i], .. ]
poly = sum c_i x^k_i
multPoly = [a0, a1, a2, .. a_m] * [ b0, b1, b2.. b_n]
a0*b0 a1*b0 +a0*b1, a2*b0+a1*b1+0*b2 ..
"""
# new poly format:
# poly = [ (power, coef), (power, coef) ...]
# powers increasing from 0
def polyMult3(p1, p2, n, mod):
answer = []
for term1 in p1:
for term2 in p2:
power = term1[0] + term2[0]
if power>n:
break
coef = (term1[1] * term2[1]) % mod
answer.append( (power, coef) )
answer.sort()
finalAnswer = []
coef = 0
power = -1
for term in answer:
if term[0]==power:
coef += term[1]
else:
if power>=0:
finalAnswer.append( (power, coef) )
power = term[0]
coef = term[1]
finalAnswer.append( (power, coef) )
return finalAnswer
def combin( n, k, mod):
if n-k<k:
k = n-k
answer = 1
for i in xrange(k):
answer = (answer * (n-i)/(i+1) ) # % mod
return answer % mod
def main():
t = int(raw_input())
for iter in range(t):
n,m = map(int, raw_input().split())
cook = []
for i in range(m):
x,y = ( map(int, raw_input().split()) )
y -= x
n -= x
cook.append(y)
cumPoly = [ (0,1) ]
for y in cook:
poly = [ (0,1), (y+1,-1)]
cumPoly = polyMult3(cumPoly, poly, n, mod)
answer = 0
for term in cumPoly:
coef = term[1]
power = term[0]
j = n-power
coef *= combin( m+j-1, j, mod)
answer = (answer + coef) % mod
print answer
## cumPoly = [0] * (n+1)
## cumPoly[0] = 1
## for y in cook:
## poly = [ 1] *(y+1) + [0] * (n-y)
## cumPoly = polyMult2(cumPoly, poly, n, mod)
##
## answer = cumPoly[n]
##
## print answer
if __name__ == "__main__":
try:
import psyco
psyco.full()
except ImportError:
pass
main()Dish Distribution CodeChef Solution in GO
package main
import "fmt"
const MOD = 1000000007
func main() {
var t int
fmt.Scanf("%d", &t)
for i := 0; i < t; i++ {
solve()
}
}
func solve() {
var n, m int
fmt.Scanf("%d %d", &n, &m)
rs := make([][]int, m)
for i := 0; i < m; i++ {
rs[i] = make([]int, 2)
fmt.Scanf("%d %d", &rs[i][0], &rs[i][1])
}
dp := make([][]int, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1)
}
dp[0][0] = 1
for i := 1; i <= m; i++ {
a, b := rs[i-1][0], rs[i-1][1]
for j := a; j <= n; j++ {
tmp := 0
for k := a; k <= b && k <= j; k++ {
tmp += dp[i-1][j-k]
if tmp >= MOD {
tmp -= MOD
}
}
dp[i][j] = tmp
}
}
ans := dp[m][n]
fmt.Println(ans)
}Dish Distribution CodeChef Solution Review:
In our experience, we suggest you solve this Dish Distribution CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Dish Distribution CodeChef Solution.
Conclusion:
I hope this Dish Distribution CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
