304 North Cardinal St.
Dorchester Center, MA 02124

# Dish Distribution CodeChef Solution

## 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());
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());
}
}

for(int i = 0; i < t; i++) {
}
}

}``````

## Dish Distribution CodeChef Solution in PYPY 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 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):
for k in range(n+1):
for i in range(k+1):

# 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):
if m>n:
m = n
for k in range(n+1):
for i in range(min(k+1,m+1)):

"""
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):
for term1 in p1:
for term2 in p2:
power = term1[0] + term2[0]
if power>n:
break
coef = (term1[1] * term2[1]) % mod
coef = 0
power = -1
if term[0]==power:
coef += term[1]
else:
if power>=0:
power = term[0]
coef =  term[1]

def combin( n, k, mod):
if n-k<k:
k = n-k
for i in xrange(k):

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)

for term in cumPoly:
coef = term[1]
power = term[0]
j = n-power
coef *= combin( m+j-1, j, mod)

##        cumPoly = [0] * (n+1)
##        cumPoly[0] = 1
##        for y in cook:
##            poly = [ 1] *(y+1)  + [0] * (n-y)
##            cumPoly = polyMult2(cumPoly, poly, n, mod)
##
##

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.

Find on CodeChef

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