Candles
TCO07 Round 3 · 2007-03-07 · by dgoodman
Problem Statement
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.)
Constraints
- n, n1, r1, n2, r2 will all be between 1 and 1000, inclusive.
- n1+n2 will be greater than n.
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.
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.
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.
56 50 20 60 16 Returns: 125
13 7 8 9 11 Returns: 149
Submissions are judged against all 86 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Candles with a public method int ceremonies(int n, int n1, int r1, int n2, int r2) · 86 test cases · 2 s / 256 MB per case