P2737 [USACO4.1] Beef McNuggets

Farmer Brown’s cows are campaigning because they heard McDonald’s is considering a new product: Beef McNuggets. The cows are trying everything to sink this terrible idea. One of their strategies is “poor packaging.” “Look,” say the cows, “if you package McNuggets using only three box sizes that hold $3$, $6$, or $10$ pieces, then you cannot satisfy customers who want to buy exactly $1$, $2$, $4$, $5$, $7$, $8$, $11$, $14$, or $17$ pieces. Poor packaging means a poor product.” Your task is to help the cows. Given the number of box types $N\ (1 \le N \le 10)$ and $N$ positive integers $b_i\ (1 \le b_i \le 256)$ representing how many McNuggets each type of box can hold, output the largest number of McNuggets that cannot be bought using these boxes (each box type is available in unlimited quantity). If every purchase request can be satisfied, or if there is no upper bound on the numbers that cannot be bought, output $0$. The largest number that cannot be bought (if it exists) does not exceed $2 \times 10^9$.

Line 1: The number of box types $N$. Lines $2$ to $N+1$: For each type, the number of McNuggets a box of that type can hold.

Output a single integer: the largest number of McNuggets that cannot be bought using the given boxes, or $0$ (if every request can be satisfied or if the set of numbers that cannot be bought is unbounded).

Problem translation from NOCOW. USACO Training Section 4.1. Translated by ChatGPT 5