P6552 Stationery Ordering (Enhanced Version).

Thanks to @肖然 (Xiao Ran) for the idea, and to @Elegia and @dengyaotriangle for their contributions to the proof of algorithm complexity (I just ported the problem).

Xiaoming’s class has a total class fund of $n$ yuan. The students plan to use the fund to collectively buy $3$ types of items: 1. Compass, $x$ yuan each. 2. Pen, $y$ yuan each. 3. Notebook, $z$ yuan each. Xiaoming is in charge of ordering the stationery. Let the ordered quantities of compasses, pens, and notebooks be $a, b, c$ respectively. His ordering rules, in order, are: 1. The $n$ yuan must be spent exactly, i.e. $ax+by+cz=n$. 2. Subject to the above condition, the number of complete sets should be as large as possible, i.e. the minimum of $a, b, c$ should be as large as possible. 3. Subject to the above conditions, the total number of items should be as large as possible, i.e. $a+b+c$ should be as large as possible. Please help Xiaoming find the optimal plan that satisfies the conditions. The data guarantees that $x>y>z$. If there are multiple solutions, output the lexicographically smallest answer $(a, b, c)$.

The input contains multiple test cases. The first line contains an integer $T$, indicating the number of test cases. The next $T$ lines each contain four integers: the class fund $n$, and the prices $x, y, z$ of the three items.

For each test case, if there is no solution, output $-1$. Otherwise, output one line with three integers separated by spaces: $a, b, c$, representing the number of compasses, pens, and notebooks.

For all testdata, $1\leq T\leq 100$, $0\leq n\leq 10^9$, $1\leq z