Maxim vs. Yogurt: The Great Discount Battle
Solution
$$$ \text{Cost}_{\text{single}} = n \cdot a $$$ $$$ b \geq 2a \quad \Rightarrow \quad \text{min cost} = n \cdot a $$$
$$$ \text{min cost} = n \cdot a $$$
$$$ \text{cost} = k \cdot b = \frac{n}{2} \cdot b $$$ $$$ \text{cost} = k \cdot b + a = \left\lfloor \frac{n}{2} \right\rfloor \cdot b + a $$$ $$$ \text{Cost}_{\text{promo}} = \left\lfloor \frac{n}{2} \right\rfloor \cdot b + (n \bmod 2) \cdot a $$$
$$$ \text{min cost} = \min\Big( n \cdot a,\ \left\lfloor \frac{n}{2} \right\rfloor \cdot b + (n \bmod 2) \cdot a \Big) $$$
$$$ 5 \cdot 4 = 20 $$$ $$$ \left\lfloor \frac{5}{2} \right\rfloor \cdot 7 + (5 \bmod 2)\cdot 4 = 2\cdot 7 + 4 = 18 $$$
$$$ \text{pairs} = \left\lfloor \frac{n}{2} \right\rfloor,\quad \text{remainder} = n \bmod 2 $$$ $$$ \text{Answer} = \min(n\cdot a,\ \text{pairs}\cdot b + \text{remainder}\cdot a) $$$
We want the minimum cost to buy exactly $$$n$$$ yogurts when:
- A single yogurt costs $$$a$$$ burles.
- A promotion lets you buy two yogurts for $$$b$$$ burles.
You may mix buying single yogurts and buying pairs. Let's reason through the options, compare costs, and derive a compact formula.
Key Observations
- Always-available baseline:
You can always buy all yogurts one-by-one. That gives the cost
- When is the promotion useful?
Buying two yogurts with the promotion costs $$$b$$$. Compare this to buying those two separately: $$$2a$$$.
- If $$$b \geq 2a$$$, the promotion is not beneficial (or is equal). Then buying every yogurt individually is at least as cheap:
- If $$$b \lt 2a$$$, the promotion saves money for pairs, so we should use as many promotions as possible.
Case Analysis
Case A — Promotion is not better ($$$b \geq 2a$$$)
Optimal strategy is to buy everything one by one:
Case B — Promotion is better ($$$b \lt 2a$$$)
We should buy as many pairs as possible:
- If $$$n$$$ is even ($$$n = 2k$$$), buy $$$k$$$ pairs:
- If $$$n$$$ is odd ($$$n = 2k+1$$$), buy $$$k$$$ pairs for $$$2k$$$ yogurts and one extra single:
We can combine both cases into a single formula:
Final Formula
Now, the answer is the minimum between the baseline and the promotion strategy:
This handles both cases because: - If $$$b \geq 2a$$$, then $$$n \cdot a$$$ will be cheaper. - If $$$b \lt 2a$$$, then the promotion plan will be cheaper.
Example Walkthrough
Let $$$n=5,\ a=4,\ b=7$$$.
- All singles:
- Promotion strategy:
Minimum cost = 18
Complexity
- Each test case is solved in $$$O(1)$$$ time (just arithmetic).
- For $$$t$$$ test cases, total complexity is $$$O(t)$$$.
Key Takeaways
- Always consider the baseline: $$$n \cdot a$$$.
- Promotion is only useful if $$$b \lt 2a$$$.
- Compact implementation:
