# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Limits
1s, 512 MB

A super shop sells only 26 items, labeled them from ‘A’ to ‘Z’. The shop stores the list of products bought by every customer as transactions.

A transaction is a set of products bought by a customer which is represented as a string. For example “ACGBD” is a transaction which means products A, C, G, B, D are bought by a particular customer. Note that all the characters of a transaction string are distinct.

At the end of the day the super shop has a big list of N transactions.

Now, let X and Y be two sets of products and [ X ∩ Y = 𝜙 ], that is X and Y have no common elements. For example X = “ABD” and Y = “CEF” is valid , whereas X = “ABC” and Y = “CDE” is not valid .

It is guaranteed that there exists at least one transaction which contains all the elements of set X.

Now you are given a list of N transactions. You have to find out the probability that a transaction string having the elements of X also contains the element of Y.

The first line contains the number of test cases **t** (1 ≤ t ≤ 20). Then t cases follow.

Each of the test case contains two integers **N** and **M** (1 ≤ N, M ≤ 1000) in the first line. Then N lines follow. Each of those line contains a string **T** (1 ≤ T ≤ 26), consists of only upper case letters, denote a transaction as described above.

Then there will be M queries. Each of the query contains two lines. First line is **X** (1 ≤ |X| ≤ 26) and the second line is **Y** (1 ≤ |Y| ≤ 26).

For each test cases first print “Case #:” in one line (where “#” is the case number, starting from 1). Then a new line follows.

Then print M lines each containing the probability P (up to 2 decimal places), that a transaction having the elements of X also contains the element of Y.

Input | Output |
---|---|

2 3 3 ABCDE ABD ACD A B AC D EA Z 2 1 XACDEGHTNOIK ZXTANIKGCH ACGH TONIK | Case 1: 0.67 1.00 0.00 Case 2: 0.50 |

71% Solution Ratio

nfs277Earliest,

anonyman637Fastest, 0.1s

nfs277Lightest, 131 kB

BruteforcekidShortest, 825B

Login to submit