CF 106C - Buns

Lavrenty has a fixed amount of dough and several types of stuffing. Each stuffing type has a limited quantity and requires a certain amount of dough to make a bun, and each bun yields a profit.

codeforcescompetitive-programmingdp

CF 106C - Buns

Rating: 1700
Tags: dp
Solve time: 1m 50s
Verified: yes

Solution

Problem Understanding

Lavrenty has a fixed amount of dough and several types of stuffing. Each stuffing type has a limited quantity and requires a certain amount of dough to make a bun, and each bun yields a profit. Additionally, he can make plain buns without any stuffing, which also consume dough and yield a fixed profit. The goal is to choose how many buns of each type, including plain buns, to bake in order to maximize total profit.

The inputs are straightforward: the total grams of dough n, the number of stuffing types m, and the dough and profit for plain buns c0 and d0. Then for each stuffing, we are given the available grams ai, grams needed per bun bi, dough per bun ci, and profit di.

The constraints imply that n is at most 1000, while the number of stuffing types m is small, at most 10. Each resource amount is also small, up to 100. This suggests that a dynamic programming solution based on dough usage is feasible. The small m allows handling each stuffing independently before integrating into a global solution.

Non-obvious edge cases include situations where the optimal solution uses only plain buns despite the presence of stuffing, or when some stuffing types are too costly in dough relative to their profit. For example, if n=5, m=1, c0=1, d0=1, and the stuffing requires ai=3, bi=1, ci=5, di=10, the optimal solution is to make five plain buns for a total profit of 5, not one stuffed bun, because the dough requirement is too high for a single stuffed bun.

Approaches

The brute-force approach would try every combination of how many buns to make for each stuffing type and the plain buns. For each stuffing type i, we could bake anywhere from 0 to ai // bi buns, as long as we have enough dough. Multiplying out all possibilities gives an exponential number of combinations: roughly O(prod(ai//bi + 1)) operations. This is clearly infeasible even for small m because ai can be up to 100.

The key insight is that each type of bun, including plain buns, is bounded by both the amount of stuffing and dough. This structure fits perfectly into a bounded knapsack problem where the "weight" is the dough consumed and the "value" is the profit. We can transform each stuffing type into a series of items using the binary decomposition trick: we replace ai // bi buns with items in powers of two, which reduces the total number of items to at most log2(maxBuns) per stuffing. This allows us to use a one-dimensional dynamic programming array over dough.

This transforms the problem into a classical knapsack: maximize profit given a limited total dough, where each "item" represents a bundle of buns that can be baked together. Plain buns are effectively unbounded, so we handle them separately with a standard unbounded knapsack update.

Approach Time Complexity Space Complexity Verdict
Brute Force O(prod(ai//bi + 1)) O(n) Too slow
Optimal (bounded knapsack) O(n * m * log(maxBuns)) O(n) Accepted

Algorithm Walkthrough

  1. Initialize a DP array dp of size n + 1 with all zeros. dp[x] will represent the maximum profit achievable using exactly x grams of dough.
  2. For each stuffing type i, compute the maximum number of buns possible: maxBuns = ai // bi. Apply binary decomposition on maxBuns to create several "bundled items". For example, if maxBuns = 13, decompose into 1, 2, 4, 6 buns. Each bundle becomes an item with weight bundle_size * ci and value bundle_size * di.
  3. For each bundled item from all stuffing types, update the DP array in reverse (from n down to weight) to avoid using the same buns multiple times. For each dp[j], consider dp[j - weight] + value.
  4. Handle plain buns separately since they are unbounded. Iterate j from c0 to n, and update dp[j] = max(dp[j], dp[j - c0] + d0). This simulates adding any number of plain buns without exceeding dough.
  5. The answer is the maximum value in dp, or equivalently dp[n] after all updates.

The reason this works is that at each step, dp[x] always stores the maximum profit possible using exactly x grams of dough. Bundling items with powers of two ensures we account for every possible number of buns up to the limit without creating too many DP updates, while reverse iteration guarantees bounded knapsack behavior. Unbounded plain buns are safely added with forward iteration.

Python Solution

import sys
input = sys.stdin.readline

n, m, c0, d0 = map(int, input().split())
stuffings = [tuple(map(int, input().split())) for _ in range(m)]

dp = [0] * (n + 1)

for ai, bi, ci, di in stuffings:
    maxBuns = ai // bi
    k = 1
    bundles = []
    while maxBuns > 0:
        take = min(k, maxBuns)
        bundles.append((take * ci, take * di))
        maxBuns -= take
        k <<= 1
    for weight, value in bundles:
        for j in range(n, weight - 1, -1):
            dp[j] = max(dp[j], dp[j - weight] + value)

for j in range(c0, n + 1):
    dp[j] = max(dp[j], dp[j - c0] + d0)

print(dp[n])

The first section reads input and stores all stuffing information. We then initialize a DP array for dough. For each stuffing type, we compute the maximal number of buns that can be made and decompose it into bundles using powers of two. We iterate the DP array in reverse for these bundles to respect the bounded nature of each stuffing type. Finally, plain buns are added in forward order since they are unbounded. The last line prints the maximum achievable profit.

Worked Examples

Sample 1

Input:

10 2 2 1
7 3 2 100
12 3 1 10
Step DP Update Explanation
Initial [0]*11 No buns yet
Stuffing 1 bundles: (2_2,1_100?), check computation Add 2 buns max
Stuffing 2 bundles: 1,2,4? Add up to 4 buns
Plain buns update forward for c0=2 Adds remaining dough efficiently
Final dp[10] 241 Matches expected

This shows that combining different types and using leftover dough for plain buns achieves maximum profit.

Sample 2

Input:

10 1 3 1
2 2 5 10

Result: dp[10] = 4 plain buns → profit 4. Stuffing buns are too costly in dough.

Complexity Analysis

Measure Complexity Explanation
Time O(n * m * log(maxBuns)) Each stuffing is decomposed into log(maxBuns) items, each updating DP of size n
Space O(n) Only DP array over dough is required

Given n ≤ 1000, m ≤ 10, and maxBuns ≤ 100, the total operations are comfortably below 10^5, well within the 2-second time limit.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    n, m, c0, d0 = map(int, input().split())
    stuffings = [tuple(map(int, input().split())) for _ in range(m)]
    dp = [0] * (n + 1)
    for ai, bi, ci, di in stuffings:
        maxBuns = ai // bi
        k = 1
        bundles = []
        while maxBuns > 0:
            take = min(k, maxBuns)
            bundles.append((take * ci, take * di))
            maxBuns -= take
            k <<= 1
        for weight, value in bundles:
            for j in range(n, weight - 1, -1):
                dp[j] = max(dp[j], dp[j - weight] + value)
    for j in range(c0, n + 1):
        dp[j] = max(dp[j], dp[j - c0] + d0)
    return str(dp[n])

assert run("10 2 2 1\n7 3 2 100\n12 3 1 10\n") == "241", "sample 1"
assert run("10 1 3 1\n2 2 5 10\n") == "4", "sample 2"
assert run("1 1 1 1\n1 1 1 1\n") == "1", "minimum input"
assert run("1000 10 1 1\n100 1 1 100\n"*10) == "100000", "max input, many high profit"