Crack the DNA

Problem code: CREDF4

All submissions for this problem are available.

Crick and Watson was the duo who discovered the Double Helix model of the DNA with its "AT GC" pairing. Now while they were working on their project, they came across an intriguiging problem. The problem was that they found many combinations of the "AT"s and "GC"s in the DNA of the same organism. To their relief, this list was exhaustive. And now, they are stuck with the problem to construct the complete DNA of the organism from the combinations that they found. The problem is that, the combinations that they found ARE be a proper subset of the master DNA Model. So now, your job is to help the legendary duo in constructing the master DNA of the organism from the given combinations. The constraint being that the length of the master DNA model should be minimum.

Input

The first line of the input would consist of the number of test cases (within 1 and 20) followed by a blank line. The first line of each test case would consist of the number of "ATGC" Combination strings (not exceeding 20 and atleast 2) followed by the combination strings on each newline. Finally, there is a blank line between each two consecutive test cases. Consider that all the string input is in UPPERCASE. The input is in the priority order i.e. the importance order of the combination strings. Consider the order of importance of the combination string input ONLY if you get two master DNA strings of the same length.

Output

For the output, the master DNA model for each test case is expected on a newline. The output is also expected in UPPERCASE only. 

Sample Input:
1

3
TAGCAT
CATGGC
GGTAG

Sample Output:
GGTAGCATGGC

Author: admin
Date Added: 17-09-2009
Time Limit: 3 sec
Source Limit: 50000 Bytes
Languages: C, CLOJ, CPP 4.0.0-8, CPP 4.3.2, F#, GO, PERL6, PYTH 3.1.2, TEXT


Comments

@admin: we can't submit in

cyberax @ 11 Dec 2011 07:45 PM
@admin: we can't submit in Python actually. even if it's told we should be able to. what is the maximum combination string length ? moreover, if the input is 1 2 TAGCAT CATTAG, what is the output ? TAGCATTAG or CATTAGCAT ? the problem statement is far from easy to understand.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions