TopCoder problem "Candles" used in TCO07 Round 3 (Division I Level Two)



Problem Statement

    In Computer Science we hold weird ceremonies -- at each ceremony we display all our candles but only n of them are lit (yeah, a binary code). Unfortunately we have 2 different types of candles: we have n1 candles that each burn at the rate r1, and n2 candles that each burn at the rate r2. (The rates are in mm/hr.)

Before each ceremony we can choose which n of our candles will be the ones that are lit during the ceremony -- we do this in an attempt to keep our candles approximately the same length. Given n, n1, r1, n2, and r2 return the number of ceremonies required for us to return our candles to uniform length. If we can never achieve uniform length, return -1.

(You may assume that our candles are arbitrarily long or that our ceremonies are arbitrarily short so we won't completely burn up any candles.)

 

Definition

    
Class:Candles
Method:ceremonies
Parameters:int, int, int, int, int
Returns:int
Method signature:int ceremonies(int n, int n1, int r1, int n2, int r2)
(be sure your method is public)
    
 

Constraints

-n, n1, r1, n2, r2 will all be between 1 and 1000, inclusive.
-n1+n2 will be greater than n.
 

Examples

0)
    
5
6
5
4
5
Returns: 2
We have 6 type 1 candles and 4 type 2's and we burn 5 candles at each ceremony. Here they burn at the same rate, so we can burn any 5 of them during the first ceremony and the other five at the next ceremony.
1)
    
3
12
4
6
2
Returns: 8
For the first 6 ceremonies we could burn fresh candles, 2 of type 1 and 1 of type 2. At that point the type 1 candles will be shorter than the type 2 candles. For the last 2 ceremonies burn 3 type 2 candles and then the other 3 type 2 candles -- all the candles will now be the same length.
2)
    
19
10
1
10
10
Returns: -1
We don't have much choice here. In each ceremony we must burn all our candles except for 1. We will never be able to burn enough of the slower burning candles to get them as short as the others.
3)
    
56
50
20
60
16
Returns: 125

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7622

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10751&pm=7622

Writer:

dgoodman

Testers:

PabloGilberto , brett1479 , vorthys , Olexiy

Problem categories:

Math