PROBLEM STATEMENT
A rechargeable battery is being charged by a solar panel, which is obtaining
its energy from candles. This battery needs to be charged for at least a time
charge_time, or the battery will not be able to get any energy from the solar
panel. For every second that the battery is charging, the charge obtained is
the square of the number of candles lit at that time. If one candle is lit,
the battery is getting one charge unit per second, if two candles are lit, four
charge units are getting stored, three candles yields nine, and so forth.
Create a class Battery that contains the method power, which takes in the
parameters candles and charge_time (minimum time the battery must be charged in
order to obtain any charge from the solar panel), and returns the maximum power
units obtainable from the candles. The battery is charged only between the
time a candle is first lit and the charge_time. Given an int[] of candle
burning times, create the best sequence of lighting the candles to obtain the
highest possible charge for the battery.
DEFINITION
Class: Battery
Method: power
Parameters: int[], int
Returns: int
Method signature (be sure your method is public): int power(int[] candles, int
charge_time);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- candles will have between 1 and 50 elements (inclusive)
- each element of candles will be an int between 1 and 200 (inclusive)
- charge_time will be an int between 1 and 200 (inclusive)
NOTES:
- once a candle is lit, it burns to completion
- the battery can be charged only if the sum of burning times for all candles
is greater than or equal to charge_time
- the battery is charging only between the time a candle is first lit and the
charge_time (if the charge_time is 10 seconds, the sum of burn times for all
the candles must be greater than or equal to 10, and the battery is only
charged between time 0 and 10 if the first candle is lit at time 0)
EXAMPLES
1) candles = {5,5}
charge_time = 10
Method returns 10
Start burning candle one at time 0, start burning candle two at time 5. They
burn for 10 seconds, only one candle burning for each second in the 10 seconds,
and hence return 1^2 * 10 = 10 power units.
2) candles = {5,5,1}
charge_time = 10
Method returns 13
Start burning candles one and three at time 0, start burning candle two at time
5. For the first second, both candle one and three burn, yielding 4 power
units. For the next 4 seconds, only candle one burns, and for the last 5
seconds, only candle two burns. (2^2 * 1) + (4 * 1^2) + (5 * 1^2) = 13 power
units.
3) candles = {5,6}
charge_time = 10
Method returns 13
Start burning candle one at time 0, start burning candle two at time 4. For
the first 4 seconds, only candle one is burning. At time = 4 seconds, light
candle two, and both candles will be lit for the next second. Candle two will
stay lit for the next five seconds after that. (1^2 * 4) + (2^2 * 1) + (1^2 *
5) = 13 power units.
4) candles = {5,6}
charge_time = 20
Method returns 0
Only 11 seconds of light can be generated by these candles, but a minimum of 20
seconds is needed to charge the battery.
5) candles = {1,1,1,1,1,1,1,1,1,1,40}
charge_time = 7
Method returns 127
All candles start burning at time 0, therefore 11 candles burn from time 0 to
1. The 40 second candle continues to burn until time 40, but only charges
until time 7. (11^2 * 1) + (1^2 * 6) = 127
6) candles =
{26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,5
2,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75}
charge_time = 200
Method returns 97885