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.

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!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Leave a Reply

Your email address will not be published. Required fields are marked *