DONALDO - DONALDO

no tags 

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.

Input

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).

Note that,
1. A specific time can occur more than once.
2. The texts are opened randomly, so the times don't have any particular(increasing/decreasing) order.
3. The duration between sending and receiving a text is negligible.
4. Intervals are inclusive. (e.g. If an interval of 5 seconds starts at 0:0:55, it will end at 0:0:59).

Output

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.

Sample Input

Output for Sample Input

2
3
8:39:17
17:17:17
21:59:59
86400
3
17:17:17
21:59:59
8:39:16
48042

Case 1: 3
Case 2: 2

 

Explanation

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.


hide comments
anshumanc007: 2018-12-22 11:37:21

Last edit: 2018-12-22 11:49:12
m2do: 2018-01-18 06:08:21

why is the output of
1
2
23:59:59
0:0:0
2

showing 1 as per spoj toolkit ?? shouldn't the output be 2 ?
Got AC :) times are not in order

Last edit: 2018-01-18 06:37:53
piyush_682: 2017-06-08 13:30:39

One of the accepted solutions is giving the output
Case 1: 3
Case 2: 0
Case 3: 23
for the input:
3
3
8:39:17
17:17:17
21:59:59
86400
0
5
23:59:08
17:17:17
21:59:59
8:39:16
17:17:17
48042
is the output correct?
I think it should be
Case 1: 3
Case 2: 0
Case 3: 4
Can anybody help?

geety: 2015-12-21 06:04:59

Hala Madrid !

Last edit: 2015-12-21 06:17:18
Dushyant Singh: 2015-06-16 19:37:24

I love time related problems! :-)

Last edit: 2015-06-19 14:07:46
Petar Bosnjak: 2015-01-24 16:57:17

Don't forget n can be 0 too!

Hussain Kara Fallah: 2014-01-31 14:33:30

Read Carefully
A specific time can occur more than once
costed me a lot of WA

Vijay Jain: 2013-07-07 04:34:33

nice question :)

sacred: 2012-07-25 20:27:12

please elaborate 2nd test case...or provide more test cases..
Problemsetter : Both of the test cases are explained in the "explanation" section.

Last edit: 2012-07-26 11:20:13
NeW AcP: 2012-07-23 13:55:46

please check my problem id 7361790. please give a test case where it is wrong.please help. what is wrong?give a hint atleast.

Problemsetter : Your code fails on many of the cases. Now I'm confused about which hint to give. :s
Reply ->give atleast one test case ,as I cannot find one.
Problemsetter : Inbox can be empty!
Reply-> thanks,ok just tell me if the concept I m using correct or i need to rethink on it on my latest submission.

Last edit: 2012-07-23 19:40:20

Added by:Bidhan
Date:2012-07-23
Time limit:0.358s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem (Used in University of Dhaka's internal contest). Alternate Writer : Shiplu Hawlader, Zobayer Hasan.