PROBLEM STATEMENT
zoidal has a potential problem. He's got a longdistance girlfriend who is
monopolizing his time by talking to him on the phone, and he finds that he
doesn't have much time to compete in TopCoder anymore. Thus, he has to make a
decision in how to best optimize his time. His girlfriend has a certain
tolerance for being ignored, but this tolerance has a negative cumulative
effect, and he must not let this tolerance drop below her "breakup" point,
otherwise he will revert to being the uber-dork that he was before they started
dating.
Every night, there may or may not be a contest. In any case, his girlfriend can
only talk to him between 6 PM and 8 PM. Consecutive nights of talking with his
girlfriend have a quadratic effect on her tolerance level, thus two consecutive
nights of talking with his girlfriend has 2 ^ 2 = 4 times the effect of only a
single conversation. Similarly, consecutive nights of not talking to his
girlfriend has a quadratic effect. Note that this quadratic effect on her
tolerance level only takes place at the end of a streak of consecutive nights
of either talking or not talking, and not on every day.
Create a class GirlFriend which contains a method optimal, which determines the
maximum number of contests that zoidal can compete in and still retain his
girlfriend. optimal takes 5 parameters, as designated in the method signature
below.
* contesttimes contains the times that the contests start at on each night,
with the first element corresponding to the first day, etc. If an element in
contesttimes is 0, there is no contest that night.
* talkdelta is the amount that the tolerance increases by with a single phone
conversation.
* notalkdelta is the amount that the tolerance decreases by with a single night
of no phone conversation.
* breakup is the threshold such that when tolerance is less than breakup,
zoidal's girlfriend ditches him.
* begintolerance is the starting tolerance level of zoidal's girlfriend.
DEFINITION
Class: GirlFriend
Method: optimal
Parameters: int[], int, int, int, int
Returns: int
The method signature is (make sure it is declared public):
int optimal(int[] contesttimes, int talkdelta, int notalkdelta, int breakup,
int begintolerance);
NOTES
* The current tolerance level cannot go above 100.
* Contests last two hours.
* If a phone conversation cannot last two hours, it will not take place at all.
* If zoidal competes, he is occupied for the entire two hours of the contest.
* If zoidal talks to his girlfriend from 6 to 8 PM, he is still able to compete
in a contest at 8 PM that night.
* For the purposes of this problem, zoidal cannot talk on the phone and compete
at the same time.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
* contesttimes will have between 1 and 50 elements, inclusive
* Every element of contesttimes will be 0, 6, 7, 8, or 9
* There will be a maximum of 20 non-zero elements in contesttimes
* talkdelta and notalkdelta will be between 1 and 100, inclusive
* breakup will be between 0 and 100, inclusive
* begintolerance will be between 0 and 100, inclusive
* breakup will be less than or equal to begintolerance
EXAMPLES
Example 1:
contesttimes = {6, 0, 8, 0}, talkdelta = 10, notalkdelta = 20, breakup = 50,
begintolerance = 60;
So, we have contests on days 1 and 3.
If zoidal competes in neither contest, the tolerance starts at 60, and since he
talks to his girlfriend for 4 days, the tolerance goes up by 10 * (4^2) = 160.
However, the tolerance cannot go above 100, so this is where the tolerance
level ends.
If he competes in the first contest and not the second, he is unable to talk to
his girlfriend on day 1, but can on day 2, 3, and 4.
Thus, tolerance starts at 60, and drops by 20 * (1^2), putting it at 40.
Although he would have talked with his girlfriend for the next 3 days, and
tolerance would have increased by 10 * (3 ^ 2) = 90, putting it at its maximum
of 100, the instant tolerance became less than breakup, he was history. Thus,
this scenario is unacceptable.
If he competes in the second contest and not the first, he is able to talk to
his girlfriend on all 4 days, since the contest on day 3 is at 8 PM, when she
hangs up. tolerance = 60 + 10 * (4^2) = 220, but maxes out at 100.
Clearly, if he competes in both contests, she will break up with him.
Thus, the maximum number of contests he can compete in is 1.
Method returns 1.
Example 2:
contesttimes = {0, 7, 6, 0, 8, 6, 0, 7, 0}, talkdelta = 5, notalkdelta = 20,
breakup = 30, begintolerance = 100
By competing in the contests on days 3, 5, 6, and 8, tolerance ends up at 70
and never dips below 30.
This is the most contests that he can compete in while maintaining his
non-uber-dork status.
Method returns 4.
Example 3:
contesttimes = {6, 0, 0, 9, 0, 8, 0, 8, 7, 7, 0, 8, 0, 6, 7}, talkdelta = 54,
notalkdelta = 44, breakup = 54, begintolerance = 69
Method returns 6.
Example 4:
contesttimes = {6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6},
talkdelta = 12, notalkdelta = 12, breakup = 12, begintolerance = 12
Method returns 10.
Example 5:
contesttimes = {7}, talkdelta = 12, notalkdelta = 12, breakup = 12,
begintolerance = 100
Method returns 1.
Example 6:
contesttimes = {7}, talkdelta = 1, notalkdelta = 1, breakup = 1, begintolerance
= 1}
Method returns 0.