解題區/解題區 - UVa

UVa 11844 - The Melding Plague

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給定每一個蛋白質在下一個時刻會變成什麼，從一開始的各種蛋白質類型的數量，是否會在哪一個時刻符合目標蛋白質種類的數量。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
2 5 4 3
CAD CELR2
ELTD1 XIRP2
POMC 1
CAD 2
SCN5A 2
XIRP2 1
ELTD1 1
POMC 1
CELR2 2
SCN5A 2
XIRP2 2
2 3 3 3
GP183 NALCN
CAC1S GP183
CAC1S 2
YCFI 1
MRP6 3
YCFI 1
MRP6 3
NALCN 2
2 3 3 1
GP183 NALCN
CAC1S GP183
CAC1S 2
YCFI 1
MRP6 3
YCFI 1
MRP6 3
NALCN 2
3 2 1 2
CAD YCFI
ELTD1 XIRP2
CAD SCN5A
CAD 1
YCFI 1
YCFI 2
0 0 0 0

Sample Output

1
2
3
4
Cure found in 1 mutation(s)
Cure found in 2 mutation(s)
Nostalgia for Infinity is doomed
Protein mutations are not deterministic

Solution

檢查是否有蛋白質轉換的模稜兩可情況，之後模擬出下一個時刻的蛋白質情況。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <stdio.h> 
#include <string.h>
#include <iostream>
#include <map>
using namespace std;
map<string, int> R;
int getLabel(string s) {
    int &x = R[s];
    return x == 0 ? x = R.size() : x;
}
#define MAXN 4096
int main() {
    int Nm, Ni, Nc, n, x, y;
    char s[MAXN];
    while(scanf("%d %d %d %d", &Nm, &Ni, &Nc, &n) == 4) {
        if(Nm + Ni + Nc + n == 0)
            break;
        R.clear();
        int Icnt[MAXN] = {}, Ccnt[MAXN] = {}, g[MAXN] = {};
        int eflag = 0;
        for(int i = 1; i < MAXN; i++)
            g[i] = i;
        for(int i = 0; i < Nm; i++) {
            scanf("%s", s);
            x = getLabel(s);
            scanf("%s", s);
            y = getLabel(s);
            if(g[x] != x && g[x] != y)	eflag = 1;
            g[x] = y;
        }
        for(int i = 0; i < Ni; i++) {
            scanf("%s %d", s, &y);
            x = getLabel(s);
            Icnt[x] = y;
        }
        for(int i = 0; i < Nc; i++) {
            scanf("%s %d", s, &y);
            x = getLabel(s);
            Ccnt[x] = y;
        }
        if(eflag) {
            puts("Protein mutations are not deterministic");
            continue;
        }
        eflag = 1;
        for(int i = 0; i <= n; i++) {			
            if(memcmp(Icnt, Ccnt, sizeof(Icnt)) == 0) {
                printf("Cure found in %d mutation(s)\n", i);
                eflag = 0;
                break;
            }
            int next[MAXN] = {};
            for(int j = 1; j <= R.size(); j++) {
                next[g[j]] += Icnt[j];
            }
            memcpy(Icnt, next, sizeof(next));
        }
        if(eflag)
            puts("Nostalgia for Infinity is doomed");
    }
    return 0;
}