The Balance#3195
Ms. Iyo Kiffa-Australis has a balance and only two types of weights to measure a dose of medicine. For example, to measure mg of aspirin using mg weights and mg weights, she can put one mg weight on the side of the medicine and three mg weights on the opposite side (Figure 1). Although she could put four mg weights on the side with the medicine and two mg weights on the other side (Figure 2), she would not choose this solution because using more weights is less convenient.
You are required to calculate how many weights are needed.
Figure 1. Measuring mg of aspirin using three mg weights and one mg weight
Figure 2. Measuring mg of aspirin using four mg weights and two mg weights
The input consists of a sequence of datasets. Each dataset is a line containing three positive integers , , and separated by a space. The following conditions hold: a \neq b, a \leq 10000, b \leq 10000, and d \leq 50000. You may assume that it is possible to measure mg by a combination of mg and mg weights. In other words, you do not need to consider cases where there is no solution.
The end of the input is indicated by a line containing three zeros separated by spaces. This line is not a dataset.
The output should contain lines, each corresponding to an input dataset (a, b, d). Each output line must contain two nonnegative integers and , separated by a space. They should satisfy the following three conditions:
You can measure mg using mg weights and mg weights.
The total number of weights x + y is minimized among all pairs of nonnegative integers satisfying the previous condition.
The total mass of weights a x + b y is minimized among all pairs satisfying the previous two conditions.
There must not be any extra characters (such as extra spaces) in the output.
Example 1