[UVA] 912 - Live From Mars
Problem I
Live From Mars
At the 26th of august 2003,
Mars was never so close to the Earth since 60.000 years. Taking
advantage of this fact, the most powerful shortsighted telescope,
Hubble, made an incredible discovery: there is life in Mars, mutant
life indeed!
Professor B. Harper, who leads the team that made this discovery, found
traces of a unicellular form of life. This kind of cell possess a new
kind of DNA: a mutant DNA that is able to specialize its inner
structure when exposed to radiations. Remarkably, B. Harper showed how
to produce any desired mutation by an appropriate radiation.
L. Kravitz, B. Harper's student, focuses its research work on a
classification of these cells based on their capacity to mutate.
Your work is to provide him a computer program that is able to find if
two mutant DNA sequences of the same length can mutate to a common DNA
sequence.
Problem
A mutant DNA sequence
is composed by the usual DNA elements, say, for the sake of simplicity, A,B,C,
and D and by mutant elements 1, 2, 3,4,5,
and so on ...
Only the mutant elements can mutate, and they mutate only once
to A, B, C or D. Then, a mutation is a process that takes a mutant DNA
sequence and transforms some (eventually all) mutant elements to normal
elements.
For instance, let be DNA1 the
following mutant DNA sequence A1CD1A2D3B2C5 and MUT the
following mutation [(1,A),(2,B),(3,C),(4,A)]
(which means mutate all occurrences of 1 into A, 2
into B, 3 into C and 4 into A).MUT
transforms DNA1 into DNA2: AACDAABDCBBC5. In this case, we
say that DNA2 is a descendant
of DNA1.
Two mutant DNA sequences of length n, x1,x2,...
,xn and y1,y2,...
,yn are equivalent under
mutation if, for all i such that 1£ i £ n, xi
and yi are both normal
DNA elements and are equal, or xi
and yi are both mutant
DNA elements (and it is not required in this case that xi and yi
are equal)
Let DNA1 and DNA2 be two mutant DNA sequences of the same length.
The shortest common mutation of DNA1
and DNA2, say MUT, is
the shortest mutation that transforms DNA1
and DNA2 into descendants which
are equivalent under mutation. MUT is the shortest in the sense
that it implies the transformation of the smallest number of mutant
elements. Note that MUT may not exist.
So, your work is to provide a program that reads two mutant DNA
sequences and replies
- NO, if there is no descendents of these two sequences that are equivalent by mutation. In other words, if there is no common mutations. Otherwise,
- YES and a print of the shortest common mutation, if there exists such a mutation.
Input
The input will contain several test cases, each of them as described below. Consecutive test cases are separated by a single blank line.
The input for the program is structured as follow:
- the first line of the input contains the length m (with m£ 200) of the considered DNA sequences
- the next m lines contain one mutant DNA element (A,B,C,D or a natural number). They code the first mutant DNA sequence.
- the last m lines contain one mutant DNA element (A,B,C,D or a natural number). They code the second mutant DNA sequence.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
The output for the program is structured as follow: in case of failure (no mutations were found) the program simply display NO. In the other case, a mutation involving n mutant elements was found and so:
- the first line is the string YES;
- the n following lines describe the shortest common
mutation; each line has the form m d
where m is a mutant element (a natural number) and d the name of the associated normal DNA element (A, B, C or D). Note that m and d are separated by a single space. The elements of the mutation are sorted by the first component (the mutant element). Thus, the mutation involving 1 will be displayed before 2.
Sample Input
7
A
1
2
B
1
D
4
1
3
B
2
3
D
4
Sample Output
YES
1 A
2 B
3 A
Sim�o Sousa, MIUP'2003
(Portuguese National ACM Programming Contest)
題目描述：
有兩個 DNA 序列，分別是 DNA1, DNA2，長度相等，而且只會有 ABCD 四種，
然而現在發生變異，部分的 ABCD 變成另外一種(以數字表示)。
現在寫一個程式，判斷是否存在一個數字只對應 ABCD 其中一個。
題目解法：
不斷地找到數字對應的 ABCD, 類似 SPFA 的更新方式。
最後有可能會存在矛盾情況，特別處理下。
#include <stdio.h>
#include <map>
using namespace std;
int main() {
int n;
char DNA1[205][10], DNA2[205][10];
int vDNA1[205], vDNA2[205];
int i, cases = 0;
while(scanf("%d", &n) == 1) {
if(cases) puts("");
++cases;
for(i = 0; i < n; i++) {
scanf("%s", &DNA1[i]);
if(DNA1[i][0] < '9')
sscanf(DNA1[i], "%d", &vDNA1[i]);
}
for(i = 0; i < n; i++) {
scanf("%s", &DNA2[i]);
if(DNA2[i][0] < '9')
sscanf(DNA2[i], "%d", &vDNA2[i]);
}
map<int, char> R;
int update, err = 0;
do {
update = 0;
for(i = 0; i < n; i++) {
if(DNA1[i][0] > '9' && DNA2[i][0] > '9') {
if(DNA1[i][0] != DNA2[i][0])
err = 1;
continue;
}
if(DNA1[i][0] <= '9' && DNA2[i][0] > '9') {
char &v = R[vDNA1[i]];
if(v == 0) {
update = 1, v = DNA2[i][0];
} else {
if(v != DNA2[i][0])
err = 1;
}
}
if(DNA1[i][0] > '9' && DNA2[i][0] <= '9') {
char &v = R[vDNA2[i]];
if(v == 0) {
update = 1, v = DNA1[i][0];
} else {
if(v != DNA1[i][0])
err = 1;
}
}
if(DNA1[i][0] <= '9' && DNA2[i][0] <= '9') {
char &v1 = R[vDNA1[i]];
char &v2 = R[vDNA2[i]];
if(v1 != 0 && v2 != 0) {
if(v1 != v2) err = 1;
}
if(v1 != 0 && v2 == 0) v2 = v1, update = 1;
if(v2 != 0 && v1 == 0) v1 = v2, update = 1;
}
}
} while(update && err == 0);
int count = 0;
for(map<int, char>::iterator it = R.begin();
it != R.end(); it++) {
if(it->second) {
count++;
}
}
if(err || count == 0) {
puts("NO");
continue;
}
puts("YES");
for(map<int, char>::iterator it = R.begin();
it != R.end(); it++) {
if(it->second) {
printf("%d %c\n", it->first, it->second);
}
}
}
return 0;
}