Stack Item and Category Coupons with an Eighty-Percent Cap

Problem Statement

You are building a discount engine for an e-commerce checkout system. The engine applies both item-specific coupons and category-wide coupons to items in a customer's cart.

Discounts stack multiplicatively rather than additively. For example, if an item receives a 20% item discount and a 10% category discount, the customer pays (1 - 0.20) * (1 - 0.10) = 0.72 of the original price, resulting in a 28% total discount.

Rules for applying discounts:

1. Each item can match at most one item-level coupon and at most one category-level coupon. If no coupon matches, the discount for that level is 0%.
2. Total savings on any single item are capped at 80% (i.e., the customer must pay at least 20% of the original item price before rounding).
3. Compute the unrounded discount amount: discount_amount = original_price * effective_discount_rate.
4. Round each item's discount amount to the nearest integer cent using round-half-up (e.g., 0.5 rounds up to 1).
5. The final price for an item is original_price - rounded_discount.
6. Return the total checkout price for the entire cart in cents.

Function Signature

def calculate_cart_total(
    items: list[dict],
    item_coupons: dict[str, float],
    category_coupons: dict[str, float]
) -> int:
    pass

Input Format

• items: A list of dictionaries, where each dict has keys:
  • "id" (str): Unique identifier for the item instance or SKU.
  • "category" (str): Category the item belongs to.
  • "price" (int): Base price of the item in cents (price >= 0).
• item_coupons: A mapping from item_id to a decimal discount rate between 0.0 and 1.0 (e.g., 0.20 for 20%).
• category_coupons: A mapping from category name to a decimal discount rate between 0.0 and 1.0.

Output Format

• Return an int representing the sum of final prices of all items in cents.

Examples

Example 1

items = [
    {"id": "apple", "category": "produce", "price": 1000},
    {"id": "steak", "category": "meat", "price": 2500}
]
item_coupons = {"apple": 0.20}
category_coupons = {"produce": 0.10, "meat": 0.15}

# Output: 2845

Explanation:

• apple: Item discount = 0.20, category discount = 0.10. Multiplicative discount = 1 - (1 - 0.20) * (1 - 0.10) = 0.28 (28%). Cap is 80%, so effective rate is 0.28. Discount = 1000 * 0.28 = 280. Final price = 1000 - 280 = 720.
• steak: Item discount = 0.0, category discount = 0.15. Multiplicative discount = 0.15. Discount = 2500 * 0.15 = 375. Final price = 2500 - 375 = 2125.
• Total = 720 + 2125 = 2845 cents.

Example 2

items = [
    {"id": "coffee", "category": "beverage", "price": 500}
]
item_coupons = {"coffee": 0.60}
category_coupons = {"beverage": 0.60}

# Output: 100

Explanation:

• Combined discount = 1 - (1 - 0.60) * (1 - 0.60) = 1 - 0.16 = 0.84 (84%).
• Capped at 80% (0.80).
• Discount = 500 * 0.80 = 400 cents.
• Final price = 500 - 400 = 100 cents.