Apply Item Coupons with Exact Per-Item Cent Rounding

Problem Statement

You are building the checkout pricing engine for a grocery chain's pilot discount program. Customers purchase multiple items and can scan coupons that apply discounts to specific items.

Each cart entry consists of:

• item_id (string): Unique identifier for the product.
• unit_price_cents (integer): Base price of one unit in cents.
• quantity (integer): Number of units purchased.

Each coupon consists of:

• coupon_id (string): Unique coupon identifier.
• item_id (string): The item it applies to.
• discount_type (string): Either "PERCENT" or "FIXED".
• discount_value (integer): For "PERCENT", an integer discount percentage between 1 and 100 (e.g., 20 means 20% off). For "FIXED", the discount amount in cents per unit.

Application Rules

1. One-to-One Matching: Each coupon applies to at most one single unit of its matching item_id. If a customer purchases 3 units of an item and applies 2 matching coupons, 2 units receive the discount and 1 unit is charged at full price. A coupon can never be split across units or applied more than once.
2. Unmatched Coupons: Coupons for items not present in the cart, or surplus coupons exceeding the purchased quantity of an item, are simply ignored.
3. Price Floor: The discounted price of an individual unit cannot drop below 0 cents.
4. Rounding Rule (Banker's Rounding): For "PERCENT" discounts, calculate the discount in cents as (unit_price_cents * discount_value) / 100.0. If this results in a fractional cent, round to the nearest integer cent using round-half-to-even (also known as banker's rounding). Specifically, if the fractional part is exactly 0.5, round to the nearest even integer (e.g., 2.5 rounds to 2, 3.5 rounds to 4). The final unit price is max(0, unit_price_cents - rounded_discount).
5. If multiple coupons apply to the same item_id, apply them in the order they appear in the coupons list.

Write a function that computes the final total cost of the cart in cents.

Function Signature

def calculate_cart_total(
    cart: list[dict],
    coupons: list[dict]
) -> int:
    pass

Constraints

• 0 <= len(cart) <= 10^4
• 0 <= len(coupons) <= 10^4
• 1 <= unit_price_cents <= 10^6
• 1 <= quantity <= 10^4
• For "PERCENT", 1 <= discount_value <= 100
• For "FIXED", 1 <= discount_value <= 10^6

Examples

Example 1:

cart = [
    {"item_id": "apple", "unit_price_cents": 150, "quantity": 2},
    {"item_id": "banana", "unit_price_cents": 75, "quantity": 1}
]
coupons = [
    {"coupon_id": "c1", "item_id": "apple", "discount_type": "PERCENT", "discount_value": 15},
    {"coupon_id": "c2", "item_id": "orange", "discount_type": "FIXED", "discount_value": 50}
]
# Output: 352

Explanation:

• "orange" coupon is ignored (not in cart).
• For "apple": unit 1 gets 15% off: 150 * 0.15 = 22.5. Half-to-even rounds 22.5 to 22. Unit price = 150 - 22 = 128 cents.
• Unit 2 of "apple" has no coupon: 150 cents.
• "banana": 1 unit at 75 cents.
• Total: 128 + 150 + 75 = 352 cents.

Example 2:

cart = [
    {"item_id": "milk", "unit_price_cents": 250, "quantity": 1}
]
coupons = [
    {"coupon_id": "c1", "item_id": "milk", "discount_type": "PERCENT", "discount_value": 15}
]
# Output: 212

Explanation:

• Discount = 250 * 0.15 = 37.5. Nearest even integer to 37.5 is 38.
• Final price = 250 - 38 = 212 cents.