# DCP-134: Special Prize Back to All Problems

Medium Divide and Conquer > Dynamic Programming

There were three friends in a university. Their names were Atik, Alomgir and Bappa. They used to eat, hang around and play all together. They were three top most students in their class and they used to understand programming very well and knew how to solve problems although they were not so good at programming. Once their sir came in the class and said ,Today i won't teach you anything, rather i will ask you a question. If anyone of you can answer that question. He will be given a very special prize. You three will be given three names of three places. You will have to find maximum common subsequence (MCS) among three names. If there are one more maximum subsequence then you will have to find lexicographically smallest MCS. Example : First place: abc Second place: bcd Third place: cde Atik ans : 2 bc ( not correct) Bappa ans: 3 abc (not correct) Alonggir ans :1 c (correct ) As if Alomgir gave the correct answer so he got that special prize. So, The same problem is given for you today, the boy among you could solve the problem he will be given the problem setter special prize. Input: ------ Input starts with an integer T (≤ 200), denoting the number of test cases.The next three lines will contain names of three places of length 1 to 50. And the string will contain alphanumeric characters only(a-z , A-Z ) and must be 'A' and 'a' difference . Output: ------- For each case, print one line containing the case number, length of MCS and the lexicographically smallest MCS . If the MCS length is 0 then just print '**T.A.T'** Sample Input ------------ 2 Aab HHH KKKK zxcvbn hjgasbznxbzmx HHzxbBb Sample Output ------------- Case 1: 0 T.A.T Case 2: 3 zxb

### Problem Limits

 Language Time Limit (seconds) C 3.00 C++ 3.00 C++14 3.00 C# 3.00 Go 3.00 Java 3.00 JavaScript 3.00 Objective-C 3.00 Perl 3.00 PHP 3.00 Python 3.00 Python3 3.00 Ruby 3.00 VB.Net 3.00

# 34/106

Solve/Submission

### Ranking

# User Language Timing
01 Robbinb1993 Cpp14 0.05s
02 killer_knight Cpp 0.06s
03 Sarwar05 Cpp14 0.09s
04 feodorv C 0.12s
05 Morass Cpp14 0.17s
06 jahid_ict Cpp14 0.30s
07 sakib_muhit Cpp 0.32s
08 tariqiitju Cpp14 0.42s
09 ssavi Cpp14 0.47s
11 Jubair_123 Cpp14 0.60s
12 Mahmudul_Tushar Cpp14 0.61s
13 mamun4122 Cpp14 0.61s
14 evan Cpp14 0.62s
15 mahbubcseju Cpp14 0.65s
16 sahedsohel Cpp14 0.68s
17 fsshakkhor Cpp14 0.69s
18 kitorp Cpp14 0.71s
19 anowar1112 Cpp14 0.71s
20 rafsan_rana Cpp14 0.72s
21 Double_O Cpp14 0.72s
22 underSpirit Cpp14 0.91s
23 Mohtasim Cpp14 1.17s
24 prateepm Cpp14 1.63s
Feedback