#P6552. Optimal Classroom Purchases
Optimal Classroom Purchases
Optimal Classroom Purchases
In this problem, you are given a class fund of n units of money, which must be spent exactly on purchasing three types of items:
- Compasses: each costs x units.
- Pens: each costs y units.
- Notebooks: each costs z units.
Let the numbers of compasses, pens, and notebooks purchased be a, b, and c respectively. The purchasing decisions follow these rules in order:
- The total cost must exactly equal n:
\( ax + by + cz = n \). - Subject to the first condition, the number of complete sets should be maximized, i.e. maximize \( \min(a,b,c) \).
- Subject to the above conditions, the total number of items \( a+b+c \) should be maximized.
- If there are multiple solutions, choose the lexicographically smallest triple \( (a,b,c) \).
It is guaranteed that \( x>y>z \). If a valid solution exists, output the corresponding triple \( (a, b, c) \).
inputFormat
The input consists of a single line containing four integers: n
, x
, y
, and z
, separated by spaces.
\( x > y > z \) is guaranteed.
outputFormat
Output three integers a
, b
, and c
(separated by a space) representing the optimal purchase counts.
sample
20 8 5 3
0 1 5
</p>