Problem Statement
Yarin likes competing at TopCoder and he seldom misses a SRM. However, since Yarin lives in Europe, the competitions are in the middle of the night. Luckily, this is usually no big problem for him as he generally doesn't have to get up early in the mornings, so he simply goes to bed after a TopCoder competition and gets up very late the day after. However, sometimes real life events occur that require him to get up early on some mornings. This can pose some problems, so Yarin wants to find the maximal amount of TopCoder competitions he can participate in given a list of TopCoder competitions and days he must get up early.
Every day Yarin gets up sometime between 7 am and 2 pm, inclusive (integer hours only, he never gets up at 7:30 am for instance). He then stays up exactly 15, 16 or 17 hours, and then goes to bed and sleeps for exactly 8 hours. The days containing a real life event force him to get up at a given time (or earlier). TopCoder competitions always start at either 2 am, 3 am or 4 am, and Yarin can not go to bed earlier than 2 hours after the competition starts. For instance, if a competition starts at 3 am, Yarin can go to bed at either 5 am or 6 am only; going to bed at 7 am is not valid since then he would have to get up at 3 pm which he never does. Also, Yarin must attend all the real life events.
Create a class TCSchedule which contains the method howMany which takes a
Each element in getup and srm corresponds to one day and night. If an element in getup is -1, it means Yarin doesn't have to get up early that day, otherwise it's the time he must get up at the latest (he might get up earlier as well, but no earlier than 7 am). If an element in srm is -1, then there is no TopCoder competition that night. Otherwise it's the time at which the TopCoder competition starts that night.
Definition
- Class:
- TCSchedule
- Method:
- howMany
- Parameters:
- int[], int[]
- Returns:
- int
- Method signature:
- int howMany(int[] getup, int[] srm)
- (be sure your method is public)
Notes
- Assume that Yarin falls asleep exactly when he goes to bed.
- In this problem, all times are integer hours only.
- The hours of the day are denoted by integers 0 to 23, inclusive, where 0 is midnight and 12 is noon.
- There are no constraints on how often there can be TopCoder competitions, except that there is at most one each night (see example 2).
- Yarin must attend all real life events, and can never get up later than the times in getup, otherwise he will miss a real life event.
- A real life event will never overlap with a SRM.
- On the first day, Yarin may get up at any time between 7 am and 2 pm (assuming that allows him to attend all real life events under the constraints above).
- The chronological order of events will be the first element in getup, the first element in srm, the second element in getup and so on.
Constraints
- srm will contain between 1 and 14 elements, inclusive.
- getup will contain between 1 and 14 elements, inclusive.
- srm will contain the same number of elements as getup.
- Each element in srm will be either -1, 2, 3 or 4.
- Each element in getup will be either -1 or between 7 and 13, inclusive.
Examples
{ 7,-1,12,-1,-1}
{ 2, 2, 2, 2,-1}
Returns: 0
On the first day Yarin has to get up at 7 am. He must therefore go to bed either at 11 pm or midnight. In any case, he won't be able to compete in the SRM that night, starting at 2 am. On the second day he can get up at either 7 am or 8 am (at most one hour different from the day before, but never earlier than 7 am). If he gets up at 8 am he still can't compete that night. On the third day he must get up at noon or earlier. He can at best get up at 9 am. He will then not be able to go to bed earlier than 2 am, the same time the SRM starts. So he can't compete this night either. On the fourth day Yarin can get up at 10 am and then go to bed 3 am. However, he must stay up to at least 4 am in order to participate in a SRM that starts 2 am, so no competition that day either. On the fifth day, he could participate in a SRM if it was at 2 am, but there is no SRM that night. Yarin can thus not compete in any of the SRMs, and the method should return 0.
{-1,13}
{-1,4}
Returns: 1
Here Yarin can get up at 1 pm on both days. On the second day he can stay up 17 hours and go to bed 6 am, which precisely allows him to compete in the SRM that night which starts at 4 am. Thus the method should return 1.
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}
{ 2, 3, 4, 2, 3, 4, 2, 3, 4, 2, 3, 4, 2, 3}
Returns: 14
TopCoder every day and no early mornings, joy!!
{ 9,-1,-1,-1,-1,12,12,-1,-1,-1,-1,-1,10,-1}
{-1,-1,-1, 3,-1,-1,-1, 4, 4, 2,-1,-1,-1, 3}
Returns: 3
Yarin can't compete in the third SRM, which takes place on the night between day 9 and 10, because then he would have to get up at 2 pm on day 10. It would then not be possible to get up at 10 am on day 13, as required, because he would need to get up 4 hours earlier in only 3 days. Nor can he compete in the SRM between day 14 and 15 as he can get up no earlier than 11 am on day 14, and must thus go to bed at the latest (11+17)%24=4 am, and the SRM that night ends at 5 am. The remaining three SRM's are possible, so the method should return 3.
{-1,13,10,-1,-1}
{-1, 2,-1,-1,-1}
Returns: 0
Even though the first real life event is at 1 pm, Yarin must get up no later than 12 am the first day since otherwise he cannot get up at 10 am on the third day. Thus, Yarin can't participate in the the SRM between day 2 and 3, so the method should return 0.
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}
{ 3,-1,-1, 2, 3, 2,-1, 4,-1, 2,-1, 3,-1}
Returns: 7
{ 9,-1,-1,-1,-1,-1,-1,-1,-1,-1,12,-1,-1}
{ 3, 4, 2,-1,-1, 2, 4, 4,-1, 2, 2, 3,-1}
Returns: 7
{13, 7,-1,-1,-1,-1,-1, 8,-1,11,-1,-1,12}
{ 3, 3, 2, 3,-1, 3, 3, 2, 3, 2,-1, 4,-1}
Returns: 0
{ 7,10,13, 9, 8,13,11,13,12,12,12,13, 8}
{ 3, 3, 2, 4, 3, 3, 2, 4, 4, 2, 2, 4, 2}
Returns: 0
{12, 8, 7, 9, 8,10, 7,-1, 7, 9, 9,13, 8, 8}
{ 4, 3, 4, 4, 4, 2, 4, 4, 2, 3, 4, 2, 2, 2}
Returns: 0
{ 9,-1,10,11,11, 7, 7,11,10,-1,-1,-1,11,11}
{ 2, 4,-1, 4,-1, 3, 3, 3, 4, 4, 3, 4, 2, 3}
Returns: 0
{ 9,13, 8,12, 9, 9,11,12, 9,12}
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}
Returns: 0
{-1}
{ 2}
Returns: 1
{ 7}
{-1}
Returns: 0
{ 7, 8, 9,10,11,12,13,12,11,10, 9, 8, 7, 8}
{ 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}
Returns: 1
{11,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, 8,-1}
{ 3, 4, 3, 2, 3, 4, 3, 4, 4, 4, 3, 3, 3, 3}
Returns: 5
{-1,-1,-1,-1,-1,-1,-1,-1,-1, 8,11, 9,-1,-1}
{ 3, 2, 3, 3, 4, 3, 4, 3, 2, 2, 4, 3, 2, 3}
Returns: 4
{-1,-1,-1,-1,-1,-1,-1,-1,-1,12,-1,-1,-1,-1}
{ 3, 4, 2, 4, 2, 4, 2, 2, 3, 2, 4, 4, 4, 3}
Returns: 13
{-1,-1,12,-1,-1,-1,-1,-1,-1,-1, 7,-1,-1,-1}
{ 3, 3, 3,-1, 2,-1, 3, 3, 4, 3, 4, 2, 3, 2}
Returns: 3
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,13,-1,-1,10}
{-1, 3, 4, 4, 3, 3, 3,-1, 3, 2, 3, 2, 4, 3}
Returns: 8
{11,-1,-1,12,-1,11,-1,13,-1,11,-1,12,-1,-1}
{ 2, 3, 4,-1,-1, 4,-1, 3,-1, 2, 3, 3, 4,-1}
Returns: 5
{ 9,-1,-1,-1,-1,-1,-1}
{-1,-1,-1, 4, 4,-1,-1}
Returns: 1
{-1,-1,-1,-1,-1,-1, 9}
{ 4, 4,-1,-1,-1,-1,-1}
Returns: 1
{11,-1,10,11,-1,12,10,13,-1,11,-1,12,-1,-1}
{ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}
Returns: 7
{11,-1, 7,13, 7,12,10,13,-1,11,-1,12,-1,-1}
{ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}
Returns: 5
{ -1, -1, -1, 7, -1, -1, 12, -1, -1, 9, -1, -1, -1, -1 }
{ 2, 2, 3, -1, 3, 2, -1, 4, 2, 3, 2, -1, 4, 3 }
Returns: 1
{ -1, -1, 12, -1, -1, -1, -1, -1, -1, -1, 7, -1, -1, 13 }
{ 3, 3, 3, -1, 2, -1, 3, 3, 4, 3, 4, 2, 3, 2 }
Returns: 3
{ 7, -1, 12, -1, 8 }
{ 2, 2, 2, 2, -1 }
Returns: 0
{ -1, -1, -1 }
{ 2, -1, -1 }
Returns: 1
{ -1, -1, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1, -1 }
{ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 }
Returns: 1
{ -1, -1, -1, -1, -1, -1 }
{ 2, 3, 4, 2, 3, 4 }
Returns: 6
{ -1, -1, 12, -1, -1, -1, -1, -1, -1, -1, 7, -1, -1, -1 }
{ 3, 3, 2, 3, -1, -1, 2, 2, 4, 2, -1, 4, 2, -1 }
Returns: 3
{ -1, 13 }
{ -1, 4 }
Returns: 1
{ 9, -1, -1, -1, -1, 12, 12, -1, -1, -1, -1, -1, 10, -1 }
{ -1, -1, -1, 3, -1, -1, -1, 4, 4, 2, -1, -1, -1, 3 }
Returns: 3