DONALDO - DONALDO
Donaldo is a great footballer. Since he is famous, he has lots of girlfriends. But the problem is, he isn't certain about the actual number of his girlfriends. So, he checked his mobile inbox. His girlfriends send him a lot of texts. But he knows that, none of them will send more than 1 text between I seconds of time interval. Given the exact times of received texts, Donaldo has to guess the minimum possible number of girlfriends he has.
The first line contains T (the number of test cases, 0 <= T <= 50). Then T test cases follows.
Each test case starts with a line with N (number of texts in Donaldo's inbox, 0 <= N <= 20000). The following N lines contain a time of the format H:M:S (H = hour, M = minute, S = second, 0 <= H <= 23, 0 <= M <= 59, 0 <= S <= 59). The i-th time is the exact time when i-th text was received (1 <= i <= N). The last line contains I (1 <= I <= 86400).
- A specific time can occur more than once.
- The texts are opened randomly, so the times don't have any particular (increasing / decreasing) order.
- The duration between sending and receiving a text is negligible.
- Intervals are inclusive. (e.g. If an interval of 5 seconds starts at 0:0:55, it will end at 0:0:59).
For each testcase, output a line containing “Case X: Y”, where X is the case number and Y is the minimum possible number of Donaldo's girlfriends.
Input: 2 3 8:39:17 17:17:17 21:59:59 86400 3 17:17:17 21:59:59 8:39:16 48042 Output: Case 1: 3 Case 2: 2
In the first test, all the texts are inside 86400 seconds duration. That means, each text is sent by a distinct girlfriend. So, number of Donaldo's girlfriends has to be greater or equal to 3.
In the second case, there are 2 possible time intervals containing 2 texts. One is containing the 1st and the 3rd time, and the other is containing the 1st and the 2nd time. So, any answer smaller than 2 is not possible.
If start = 17 and time interval = 1000, segment is (17,17+999) instead of (17,17+1000) !
Nice problem :)
why is the output of
One of the accepted solutions is giving the output
Hala Madrid !Last edit: 2015-12-21 06:17:18
I love time related problems! :-)Last edit: 2015-06-19 14:07:46
Don't forget n can be 0 too!
Hussain Kara Fallah:
nice question :)
please elaborate 2nd test case...or provide more test cases..