P16199 [ROIR 2014 Day 2] Sweets

In City P, there is an amazing candy factory, and the main character Xiao Ming lives there. One day, Xiao Ming plans to take a train to City M to visit his good friend Xiao Hua, and he wants to bring as many boxes of delicious sweets as possible as a gift. Each box of sweets has size $a \times b \times c$ centimeters, representing length, width, and height. To pack these boxes, Xiao Ming plans to use a large rectangular box (a cuboid). All sweet boxes must keep their original orientation, and they must all be neatly arranged in the same direction. The size of the large box can be chosen freely, but according to railway transport rules, the sum of the three side lengths of the box must not exceed $N$ centimeters. Please help Xiao Ming write a program. Given $N$, $a$, $b$, and $c$, compute the dimensions of a box so that it can hold the maximum number of sweet boxes.

The first line contains four integers separated by spaces: $N, a, b, c\ (1 \le N, a, b, c \le 10^9)$.

Output three integers, representing the length, width, and height of the box chosen by Xiao Ming, such that the box can hold the maximum number of sweet boxes. If there are multiple answers, output any one.

In the first sample, the best choice is a $3 \times 4 \times 3$ cm box. It can place $3$ boxes along the length, $2$ along the width, and $1$ along the height, for a total of $6$ boxes of sweets. In the second sample, to fit at least two boxes, the box must be at least $8 \times 3 \times 4$, and the sum of the three sides is $15$ cm. In fact, the maximum is still only $1$ box. A box like $9 \times 3 \times 2$ also satisfies the condition, even though it is not the smallest. ### Scoring For the $30$-point testdata, $N \le 1000$. For the $60$-point testdata, $N \le 100\,000$. Translation source: GPT 4.1 mini. Translated by ChatGPT 5