FATAWY - Fatawy

no tags 

Fatawy is one of the most popular social networking site in Egypt during the last period. Every user is posting Fatwa through his profile to share his thoughts with his followers. And everyone can re-post a Fatwa and make some small modifications to this Fatwa before re-posting it.

Zezo was interested to analyze all Fatawy from his followers and know what are the trending topics they are discussing in Egypt on a given day. So he tried to model a system to extract some features from every Fatwa, such that every Fatwa can be represented by at most 10 features and every feature is represented by one Capital Alphabetic character. And through his system he decided to define a relation between Fatawy, that's fatwa 'A' is on the same topic as Fatwa 'B', if values of fractions length(lcs)/length(A) and length(lcs)/length(B) in percent must both be bigger than TH where: lcs is the longest common subsequence of the feature vector of Fatwa 'A' and feature vector of Fatwa 'B' and TH is a threshold percentage of the Fatwa length. If Fatwa 'A' is on the same topic of Fatwa 'B', and Fatwa 'A' is on the same topic of Fatwa 'C', then Fatwa 'B' is on the same topic of fatwa 'C'. (See sample 1 for details).

So as you all know that Zezo is not that good at programming and implementing this system, he will just help you by giving you the feature vector of every Fatwa, and he kindly ask you to find the number of different topics in that day.

Note:
The longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two). And it is good to notice that substrings are consecutive parts of a string, while subsequences need not be.

Input

The first line of input contains an integer T that represents the number of test cases. Every following test case will start with a line contains two integers N and TH (1 <= N <= 500) number of Fatway in a given day and TH is an integer number in the interval ]0, 100[ which is the threshold percent as explained in the problem description, followed by N lines every line contains a single string Fi of uppercase characters where 1 <= length(Fi) <= 10.

Output

For each test case, output on a single line “Case #T:” where T is the number of the test case, followed by a line contains the number of trending topics in that day.

Example

Input:
2
3 60
ABC
ABB
ACC
5 80
BCCBC
AAABB
CACBC
CABCB
ABCAB Output: Case #1:
1
Case #2:
2

Explantation:

the LCS between (ABC,ABB) = 2, Len(ABC) = 3, Len(ABB)=3, Len(ACC)=3
LCS / Len(ABC) = 66.66 >= 60% && LCS / Len(ABB) = 66.66 >= 60%
so ABC and ABB considered to be on the same topic.

The same Applies for ABC and ACC: (ABC,ABB) are on the same topic, (ABC,ACC) are on the same topic, so (ABC, ACC, ABB)
are considered to be on the same topic.

hide comments
Sigma Kappa: 2017-09-21 21:01:51

Should be moved to tutorial.

Vipul Srivastava: 2017-06-13 20:38:59

Its not that both should be bigger than TH, instead both should be bigger or equal to TH.

shikhar jindal: 2016-04-30 12:25:07

let n = 3 , th = 50.
s1 = AB
s2 = BC
s3 = CD
What will be the answer for this case?

shikhar jindal: 2016-04-30 10:20:42

what will be the number of test cases?

Mohit Pandey: 2015-06-20 19:41:03

12 WAs for using real number arithmetic, changed it to integer and typecasted double for fun and AC!!

rishabhtwr07: 2015-01-14 21:14:40

@Mostafa "If Fatwa 'X' is on the same topic of Fatwa 'Y', and Fatwa 'X' is on the same topic of Fatwa 'Z', then Fatwa 'Y' is on the same topic of fatwa 'Z'" how so ?? lets say X = "AB" ; Y = "AA" ; Z = "BB" if TH =50 ; (X -> Y) and (X -> Z) but Y is not on the same topic of Z .. . pls explain !

edit : finally ac :)

Last edit: 2015-01-15 20:38:57
Sudarshan K: 2014-12-19 11:53:55

When used C++ string - AC :) WA with char arrays.

Rishav Goyal: 2014-02-10 17:18:13

don't apply if( f(arg)), gives WA on spoj!.

Aradhya: 2013-03-31 06:30:31

for kids ! Enjoy babies :)

edit: good luck in hell

Last edit: 2014-01-29 15:01:55
:D: 2013-01-31 11:10:47

Can you make it more clear in the description that the percentage actually means length percentage. Simply write "Values of fractions len(lcs)/len(A) and len(lcs)/len(B) in percent must both be bigger than TH." Right now it's very hard to read and Only the explanation clears it.

Really consider the change, because the problem itself is great, it deserves a clear translation :)

Last edit: 2012-11-11 13:17:37

Added by:Mostafa Saad Ibrahim
Date:2012-11-10
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:11th Egyptian Collegiate Programming Contest