#P6552. Optimal Classroom Purchases

    ID: 19765 Type: Default 1000ms 256MiB

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:

  1. The total cost must exactly equal n:
    \( ax + by + cz = n \).
  2. Subject to the first condition, the number of complete sets should be maximized, i.e. maximize \( \min(a,b,c) \).
  3. Subject to the above conditions, the total number of items \( a+b+c \) should be maximized.
  4. 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>