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 Setter:

Anowar Hossain Anu

Please login to submit solution to this problem.

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

Problem Stats




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

Your feedback is our precious!

Or call +88 02 9853138 for support