You are opening a robotic coffeehouse ("Untouched by human hands!" will be your motto).
Your customers can order regular or decaffeinated coffee by the ounce. The machinery processes
two orders at once: one order of regular and one order of decaffeinated. Upon receiving the orders,
the machinery measures and pours the two drinks into serving cups. Your task is to calculate how
many seconds the customers will have to wait for their drinks.
The machinery includes measuring cups of several sizes, but not enough sizes to directly measure all
the drink sizes on the menu. Instead, the machinery may measure each of the drinks in several steps.
For example, to fulfill an order of 1 ounce of decaffeinated coffee using measuring cups that
hold 4, 6, and 9 ounces, respectively, the machinery might follow these steps:
- Pour 4 ounces of coffee from the reservoir into the 4-ounce cup.
- Pour 4 ounces of coffee from the 4-ounce cup into the 9-ounce cup.
- Pour 6 ounces of coffee from the reservoir into the 6-ounce cup.
- Pour 5 ounces of coffee from the 6-ounce cup into the 9-ounce cup, filling the 9-ounce cup to capacity and leaving 1 ounce in the 6-ounce cup.
- Pour the remaining ounce from the 6-ounce cup into the serving cup.
All pouring actions take 1 second to complete, but actions that involve different cups may be performed simultaneously.
In this example, step 2 could be performed at the same time as step 3, so the drink could be served after 4 seconds.
A single pouring action can pour coffee from the reservoir to a measuring cup, from a measuring cup to another measuring cup, from
a measuring cup to the reservoir, or from a measuring cup to the serving cup. No measuring cup, serving cup, or reservoir may be
involved in more than one pouring action simultaneously. For example, you cannot pour coffee from two different measuring cups into
the same reservoir at the same time.
A pouring action ends when the source cup is empty or
when the destination cup is filled to capacity, whichever comes first. The reservoir is large enough that you can
neither empty it nor fill it to capacity.
A serving cup has more capacity than needed by the order (to leave room for cream), but you cannot pour coffee out
of a serving cup, so you must be careful not to pour more coffee into the serving cup than was ordered.
The system handles regular and decaffeinated coffee simultaneously. There are separate reservoirs and serving cups for the
two kinds of coffee, but they both use the same measuring cups. Naturally, however, no measuring cup is permitted to hold
both kinds of coffee at the same time. Similarly, regular coffee may not be poured into the decaffeinated reservoir or serving cup,
and vice versa.
You will be given the sizes of the measuring cups in a int[] cups. In addition, you will be given
the sizes of the two orders, regular and decaf. You must calculate and return the minimum time in seconds
needed to complete both orders. If it is impossible to complete one or both orders, return -1.
|