解題區/解題區 - UVa

UVa 1031 - Insecure in Prague

contents

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

Problem

給一段密文，輸出最長的明文，如果最長明文有多個，則輸出 Codeword not unique。

加密的工序為

  • 決定四個參數 s, t, i, j
  • 類似殺人遊戲般，一開始有 m 個空位，初始位置於 s 開始數，每 i 個空位就填入明文的下一個字符。
  • 然後重複動作填入第二次明文，但是起始位置 t，每 j 個空位填入。
  • 剩餘位置隨機填入字符。

Sample Input

1
2
3
4
APPURAAURGEGEWE
ABABABAB
THEACMPROGRAMMINGCONTEST
X

Sample Output

1
2
3
Code 1: PRAGUE
Code 2: Codeword not unique
Code 3: Codeword not unique

Solution

題目中有一段

Starting with the first empty slot in or after position t in string …

看起來 t 一點也不重要。也就是不用特定對 t 窮舉參數，將每個可以填入的位置都嘗試過當初始位置。

窮舉的順序，窮舉 s, n, i 可以在第一次填入工序中，得到明文結果。然後在第二步處理中，檢查是否明文填入時時候對應到原本的密文。

在窮舉前，可以事先計算殺人遊戲的殺戮順序，好在窮舉時得到明文結果。在第二步窮舉時，由於已經將部分明文填入好，剩餘的空格少了快一半，必須將其壓縮再一起，重新使用殺人遊戲的填入方式。

這一題很卡常數，很優化就優化，寫到眼神崩盤。

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <stdio.h>
#include <string.h>
#include <set>
#include <iostream>
#include <vector>
using namespace std;
vector<int> putOrder[51][51]; // [m][i]
int main() {
    for (int m = 2; m < 50; m++) {
        for (int i = 0; i < m; i++) {
            int visited[50] = {}, pos = 0, skip = 0;
            putOrder[m][i].push_back(pos), visited[pos] = 1;
            for (int p = 1; p < m; p++) {
                skip = i % (m - p);
                while (skip >= 0) {
                    pos++;
                    if (pos >= m)	pos = 0;
                    if (!visited[pos])
                        skip--;
                }
                visited[pos] = 1;
                putOrder[m][i].push_back(pos);
            }
        }
    }
//	for (int i = 0; i < putOrder[15][6].size(); i++) // example
//		printf("%d\n", (putOrder[15][6][i] + 1)%15);
    char text[64];
    int cases = 0;
    while (gets(text)) {
        if (!strcmp("X", text))	break;
        int m = strlen(text);
        int appear[128] = {};
        for (int i = 0; text[i]; i++)
            appear[text[i]]++;
            
        int mxlen = 1, remainUsed[64];
        set<string> ret[64];
        for (int s = m-1; s >= 0; s--) {
            if (appear[text[s]] < 2) // must not start alphabet			
                continue;
            for (int n = m/2; n >= mxlen; n--) {
                if (ret[n].size() > 1)	continue;
                char plain[128];
                for (int i = 0; i < m; i++) {
                    if (ret[n].size() > 1)	continue;
                    int cnt[128] = {}, used[64] = {};
                    int ok = 1;
                    for (int p = 0; p < putOrder[m][i].size() && p < n; p++)
                        plain[p] = text[(putOrder[m][i][p] + s)%m], used[(putOrder[m][i][p] + s)%m] = 1;
                    plain[n] = '\0';
                    for (int p = 0; p < n; p++) {
                        cnt[plain[p]]++;
                        if (cnt[plain[p]] * 2 > appear[plain[p]])
                            ok = 0;
                    }
                    if (!ok)	continue;
                    if (ret[n].find(plain) != ret[n].end())
                        continue;
                        
                    int mm = 0;
                    for (int p = 0; p < m; p++) {
                        if (!used[p])
                            remainUsed[mm++] = p;
                    }
                    for (int t = 0; t < mm; t++) {
                        if (plain[0] != text[remainUsed[t]])	
                            continue;
                        if (ret[n].size() > 1)	continue;
                        for (int j = i + 1; j < m; j++) {
                            if (ret[n].size() > 1)	continue;
                            int visited[50] = {};
                            int pos = t, skip = 0, ok2 = 1;
                            visited[pos] = 1;
                            for (int p = 1; p < n; p++) {
                                skip = j % (mm - p);
                                while (skip >= 0) {
                                    pos++;
                                    if (pos >= mm)	pos = 0;
                                    if (!visited[pos])
                                        skip--;
                                }
                                if (plain[p] != text[remainUsed[pos]]) {
                                    ok2 = 0;
                                    break;
                                }
                                visited[pos] = 1;
                            }
                            if (ok2) {
                                if (n > mxlen)
                                    mxlen = n;
                                ret[n].insert(plain);
                            }
                        }
                    }
                }
            }
        }
        printf("Code %d: ", ++cases);
        for (int i = m/2; i >= 0; i--) {
            if (ret[i].size()) {
                if (ret[i].size() == 1)
                    printf("%s\n", ret[i].begin()->c_str());
                else
                    puts("Codeword not unique");
                break;
            }
        }
    }
    return 0;
}
/*
APPURAAURGEGEWE
ABABABAB
THEACMPROGRAMMINGCONTEST
X
*/