Problem D
Raðgreining 2
Languages
en
is
You work at a research lab where the genetic data of the virus 2019-nCoV, better known as COVID, is being sequenced. Using sequencing the structure of its DNA is being analyzed. The DNA sequence of the virus is a string of length $n$ containing only the letters G, T, A and C.
The method your research lab uses can only sequence a small section of the DNA sequence at a time. As an example, if the DNA sequence of the virus is of length $6$, the method could be used to sequence the section starting with letter number $1$ and ending with letter number $4$ in its DNA and then sequence the section starting with letter number $3$ and ending with letter number $6$. If the first sequencing returned GCAT and the second returned ATTC, then it could be deduced that the DNA sequence of the virus is GCATTC.
Using this method various pieces of the DNA sequence of the virus have been sequenced and all that is left to do is piece them together. Whoops! You drop all the DNA sections that have been sequenced onto the floor and now you don’t know how they are oriented. For example the second section sequenced could now be CTTA.
Given the pieces that have been sequenced, each being either correct or reversed, and where each of those pieces start, write a program that pieces them together to find the a possible DNA sequence of the virus.
Input
The first line of the input contains two integers $n$ and $m$ ($1 \leq n, m \leq 500$), the length of the DNA sequence and the number of sections that have been sequenced.
Then there are $m$ lines, one for each section that has been sequenced. Each of these lines starts with an integer $s$ ($1 \leq s \leq n$), the position at which this section starts, followed by the section itself which is a string of length $k$ ($1 \leq k \leq n - s + 1$) which contains only the letters G, T, A and C.
Output
Print a single line containing the letters of a possible DNA sequence for the virus. If many possible DNA sequences are possible, any of them can be printed. If no DNA sequence is feasible, instead simply print Villa.
Stigagjöf
|
Group |
Points |
Constraints |
|
1 |
20 |
$n\leq 100$, $m\leq 10$ |
|
2 |
20 |
$n\leq 25$, $m\leq 100$ |
|
3 |
20 |
Each section has length exactly $3$ |
|
4 |
20 |
Each section has length exactly $15$ |
|
5 |
20 |
No further constraints |
| Sample Input 1 | Sample Output 1 |
|---|---|
9 3 1 GCAT 3 CTTA 7 AAC |
GCATTCAAC |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 2 3 AAAA 8 GGG |
GTAAAAAGGG |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 2 3 AAAA 6 GGG |
Villa |
