Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Mathematics and Computer Science
Fragment Assembly
Time Limit: 2000ms, Special Time Limit:4000ms, Memory Limit:32768KB
Total submit users: 3, Accepted users: 1
Problem 10009 : No special judgement
Problem description
  A single DNA molecule is a string from an alphabet containing the four characters A(denine), G(uanine), and T(hymine), and C(ytosine)¡ªthe first letters of the names of four nitrogen bases. Because we have no way of getting the entire string directly for DNA, we adopt an idea to break them up into fragments at random locations, and obtain a large number of substrings of the string. Because of how they are created, many of these substrings will overlap. We want to reconstruct the sequence. There is not generally a unique solution, so we will find one that yields the shortest possible string. For example, here are a set of fragments aligned above a strand they might come from:


Input
  The input to your program will consist of one or more sets of data in free format. Each set starts with an integer, N(1 <= N <= 15), followed by N fragments. Each fragment is a string of no more than 100 characters from the (upper-case) AGTC alphabet. A set starting with the integer 0 terminates the input.

Output
  for the output, printing in ten groups of three per line (or possibly fewer at the end of the string) and leaving a blank line between sets. If there are several such strings of shortest length, find the smallest in alphabetical/lexicographical order.

Sample Input
10
TGGAGGGGGTA
GTTATTGCCAACAGCA
AGCAGTGG
TACTGTTGCAT
AGGCCTGATCGCAC
GGGGGTATCGCAGGCCT
GCATGTTG
AACAGCAGTGGA
ATGTTGGAGTTATT
CATGTTGGAGTT
0
Sample Output
TAC TGT TGC ATG TTG GAG TTA TTG CCA ACA
GCA GTG GAG GGG GTA TCG CAG GCC TGA TCG
CAC
Problem Source
  HNU Contest 

Submit   Discuss   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:322 today,10600156 total, since 2010-05-07