32319번 - Espresso Made Your Way 다국어

You have a new job. You can honestly say that coffee is not your cup of tea. You have many customers that ask for a particular ratio of coffee to milk. You don't have the ability to make arbitrary measurements. You have two cups. Both cups are the same size. You have a machine that dispenses pure coffee, and another machine that dispenses pure milk.

You can completely fill one empty cup with coffee and the second empty cup with milk. You can also take these two full cups and create a mix such that the result will have exactly half of each cup, i.e., half coffee and half milk. So, you have created a mix (a cup) that is half coffee and half milk but, unfortunately, you have wasted a full cup of ingredients (the second half of coffee and the second half of milk).

Now that you have a cup that is half coffee and half milk, you can fill the second cup with coffee or fill the second cup with milk. Then, you can mix your two cups to create a cup with a different coffee-to-milk ratio. Note that, when mixing two cups, you use exactly half of each cup and waste exactly half of each cup.

By repeating the above process, you can make some coffee-to-milk ratios but some ratios are literally impossible.

Given the tolerance range a customer has for their coffee-to-milk ratio, determine the least amount of ingredients you will waste assuming you prepare the customer's order optimally.

There is only one input line; it contains four integers: C₁, M₁, C₂, and M₂ (0 ≤ C₁, M₁, C₂, M₂ ≤ 10⁶) representing the coffee-to-milk ratio range the customer accepts. More specifically, the ratio can be anywhere from C₁ coffee parts per M₁ milk parts to C₂ coffee parts per M₂ milk parts. You are guaranteed that:

• The two ratios will not be identical.
• C₁ + M₁ > 0
• C₂ + M₂ > 0
• C₁ / (C₁ + M₁) ≠ C₂ / (C₂ + M₂)

Print one integer representing the least number of cups of ingredients wasted assuming you prepare the customer’s order optimally.