TopCoder problem "Decaffeinated" used in TCCC '04 Round 3 (Division I Level Three)

Problem Statement


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:

  1. Pour 4 ounces of coffee from the reservoir into the 4-ounce cup.
  2. Pour 4 ounces of coffee from the 4-ounce cup into the 9-ounce cup.
  3. Pour 6 ounces of coffee from the reservoir into the 6-ounce cup.
  4. 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.
  5. 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.



Parameters:int[], int, int
Method signature:int wait(int[] cups, int regular, int decaf)
(be sure your method is public)


-You may not pour coffee on the floor.


-cups contains between 1 and 3 elements, inclusive.
-Each element of cups is between 1 and 12, inclusive.
-regular and decaf are both between 1 and 16, inclusive.


{ 1 }
Returns: 22
Pouring 1 ounce of coffee first from the reservoir into the measuring cup, and then from the measuring cup into the serving cup, takes 2 seconds. Repeat this process a total of 11 times for a total of 22 seconds.
{ 1, 1 }
Returns: 12
The same as the previous example, but now you can use two measuring cups simultaneously.
{ 3, 6, 12}
Returns: -1
{ 10, 11, 12 }
Returns: 11
{ 11, 12, 11}
Returns: 31

Problem url:

Problem stats url:




lbackstrom , brett1479

Problem categories:

Recursion, Search