UCV2013G - Schedules

no tags 

PEPE the singer has released a new song. He wants to control how many times his songs is played on RUMBA FM radio station. PEPE has hired two companies (A and B) to perform this task. Every day, they give him a schedule indicating the time when the song has been played on the radio. Song always takes the same number of seconds to play, so end times are not important. We are only interested in start times.

On the first day PEPE received both schedules. They were almost identical. He verified that each entry of A corresponds to exactly one entry in B. He simply took a pencil, and he marked one entry in A, and then the corresponding entry in B. He continued with this approach as long as unmarked entries exist. The second day PEPE again received both schedules, but he found that the number of entries in both schedules is not the same. Moreover, the times did not match at all due to a human error. He said, "Oh Gosh!, I have to reconcile both schedules, finding the best possible match between them". He only trusts the entries that can be matched in both schedules. But how to match them? PEPE started by deciding how many seconds of error (difference) he is able to tolerate for two matched entries. Then he tried to find the largest number of possible matches. For equally large matchings, he is interested in smallest average time difference in seconds. Unfortunately, it may take too long since his new song are very popular, having many hits in RUMBA FM. So, we need your help to perform this task automatically.

Input

The input consists in several test cases. Each test case starts with a line containing three integer numbers Na, Nb, and S, separated by single spaces. Na and Nb are the number of entries in A and B respectively (1 <= Na, Nb <= 200), and S is the tolerance in seconds (0 <= S <= 7200). The second line contains Na time stamps in the format hh:mm:ss separated by single spaces. The third line contains Nb time stamps in same format as the previous one. Note that all start times are in the same day.

The end of the input is an empty test case, where Na = Nb = S = 0 and should not be processed.

Output

For each test case, the output is a single line containing an integer K and floating point number V rounder to one decimal place. K is the largest number of matches between schedule A and schedule B. V is the average time difference in seconds between the K matched entries. In case there is no possible match, your program should instead print "No matches"

Example

Input:
4 2 120
03:00:00 03:00:59 07:40:00 12:40:04
02:59:14 12:41:45
3 2 60
03:00:59 07:40:00 12:40:04
02:59:14 12:41:45
0 0 0 Output: 2 73.5
No matches

hide comments
Jacob Plachta: 2014-02-20 15:56:19

I was only able to get AC (in C++) by subtracting 10^-9 from the time difference before outputting it, presumably due to answers ending in 0.05 and being rounded differently in different languages...

Mostafa 36a2: 2013-08-05 02:30:27

@:D I think the main misunderstood was that the problem not clearly tell that we need to find the largest match with minimum difference ,
btw i've noticed that you changed
"Oh My God!" to "Oh Gosh!"
that was clearer ;)

:D: 2013-08-04 19:47:07

Did some changes in description. Hope it's clearer now. The original version however wasn't all that bad.

Hector Navarro: 2013-08-01 15:37:55

@Risyanggi: not necessarily

Risyanggi Azmi Faizin: 2013-07-31 23:25:32

@navarro is the time stamps test cases sorted?

Hector Navarro: 2013-07-29 13:08:30

@Hamdi: your code fails on several test cases

Hamdi Ahmadi Muzakkiy: 2013-07-28 08:55:12

@Hector Navarro please check my code id 9735204.. i don't know why it giving WA

Rocker3011: 2013-07-27 00:38:11

S can be 0 ;) remember that while doing the input condition, costed me 2 W.A

Arika Saputro: 2013-07-26 22:33:49

thanks for this problem :D

Hector Navarro: 2013-07-26 19:32:04

@Mitch: there are about 200 cases. The difference between 00:00:00 and 23:59:59 would be 86399 seconds. And you don't have to care about the songs duration


Added by:Hector Navarro
Date:2013-07-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Local UCV 2013. Rhadamés Carmona