解題區/解題區 - UVa

UVa 1398 - Meteor

Problem

進行天文觀測，天空上有 n 個流星，以及拍攝的區域。

給定每一個流星的起始位置與速度，請問在哪一個時刻可以拍到最多顆流星在拍攝區域內部。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2 
4 2 
2 
-1 1 1 -1 
5 2 -1 -1 
13 6 
7 
3 -2 1 3 
6 9 -2 -1 
8 0 -1 -1 
7 6 10 0 
11 -2 2 1 
-2 4 6 -1 
3 2 -5 -1

Sample Output

1
2
1 
2

Solution

將每一個流星進入和離開拍攝區域的時間求出，並且組合成 (enter_time, 1), (leave_time, -1) 的方式，根據時間由小排到大，利用掃描線算法統計累計的最大值即可。

求流星進出區域的時間，可以將 x, y 座標分開考慮，對進入時間取最大值、離開時間取最小值。

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
// sweep line algorithm
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int LCM = 2520; // gcd(1, 2, 3, ..., 10) = 2520, /vx, /vy, vx, vy <= 10
int W, H;
pair<int, int> getTime(int sx, int sy, int vx, int vy) {
    int enter = 0, leave = INF;
    if (vx == 0) {
        if (sx <= 0 || sx >= W)
            leave = 0;
    } else if (vx < 0) {
        enter = max(enter, (sx - W) * LCM / (-vx));
        leave = min(leave, (sx - 0) * LCM / (-vx));
    } else {
        enter = max(enter, (0 - sx) * LCM / (vx));
        leave = min(leave, (W - sx) * LCM / (vx));
    }
    if (vy == 0) {
        if (sy <= 0 || sy >= H)
            leave = 0; 
    } else if (vy < 0) {
        enter = max(enter, (sy - H) * LCM / (-vy));
        leave = min(leave, (sy - 0) * LCM / (-vy));
    } else {
        enter = max(enter, (0 - sy) * LCM / (vy));
        leave = min(leave, (H - sy) * LCM / (vy));
    }
    return make_pair(enter, leave);
}
int main() {
    int testcase, N;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &W, &H);
        scanf("%d", &N);
        
        vector< pair<int, int> > D;
        for (int i = 0; i < N; i++) {
            int sx, sy, vx, vy;
            scanf("%d %d %d %d", &sx, &sy, &vx, &vy);
            pair<int, int> t = getTime(sx, sy, vx, vy);
            if (t.first < t.second) {
                D.push_back(make_pair(t.first, 1));
                D.push_back(make_pair(t.second, -1));
            }
        }
        
        sort(D.begin(), D.end());
        int ret = 0;
        for (int i = 0, s = 0; i < D.size(); i++) {
            s += D[i].second;
            ret = max(ret, s);
        }
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1342 - That Nice Euler Circuit

Problem

一筆畫完成一個簡單多邊形，請問有多少個區域。

Sample Input

1
2
3
4
5
5
0 0 0 1 1 1 1 0 0 0 
7 
1 1 1 5 2 1 2 5 5 1 3 5 1 1 
0

Sample Output

1
2
Case 1: There are 2 pieces. 
Case 2: There are 5 pieces.

Solution

利用尤拉公式$V - E + F = 2$ 來完成，藉由線段交找到所有頂點集合，去除掉重複點後，檢查邊的數量，如此一來就可以找到面的數量。

特別小心共線計算。

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
// Euler characteristic, V - E + F = 2
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <assert.h>
#include <vector>
#include <string.h>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    bool operator!=(const Pt &a) const {
    	return !(a == *this);
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
    double length() {
        return hypot(x, y);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
const double pi = acos(-1);
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0): s(a), e(b), label(l) {
    }
    bool operator!=(const Seg &other) const {
        return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
    }
};
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if (cmpZero(cross(as, at, bs) * cross(as, at, bt)) < 0 &&
        cmpZero(cross(bs, bt, as) * cross(bs, bt, at)) < 0)
        return 1;
    return 0;
}
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
    return acos(dot(va, vb) / va.length() / vb.length());
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
int inPolygon(vector<Pt> &p, Pt q) {
    int i, j, cnt = 0;
    int n = p.size();
    for(i = 0, j = n-1; i < n; j = i++) {
        if(onSeg(p[i], p[j], q))
            return 1;
        if(p[i].y > q.y != p[j].y > q.y &&
        q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
        cnt++;
    }
    return cnt&1;
}
double polygonArea(vector<Pt> &p) {
    double area = 0;
    int n = p.size();
    for(int i = 0; i < n;i++)
        area += p[i].x * p[(i+1)%n].y - p[i].y * p[(i+1)%n].x;
    return fabs(area) /2;
}
Pt projectLine(Pt as, Pt ae, Pt p) {
    double a, b, c, v;
    a = as.y - ae.y, b = ae.x - as.x;
    c = - (a * as.x + b * as.y);
    v = a * p.x + b * p.y + c;
    return Pt(p.x - v*a / (a*a+b*b), p.y - v*b/ (a*a+b*b));
}
// maybe collinear !!!!!!!!
int main() {
    const int MAXN = 305;
    int n, cases = 0;
    Pt D[MAXN];
    while (scanf("%d", &n) == 1 && n) {		
        int V = 0, E = 0; 
        vector<Pt> SV;
        
        for (int i = 0; i < n; i++)
            D[i].read(), SV.push_back(D[i]);
        for (int i = 0; i+1 < n; i++) {
            for (int j = i+1; j+1 < n; j++) {
                if (intersection(D[i], D[i+1], D[j], D[j+1])) {
                    Pt p = getIntersect(Seg(D[i], D[i+1]), Seg(D[j], D[j+1]));
                    SV.push_back(p);
                }
            }
        }
        
        sort(SV.begin(), SV.end());
        SV.resize(unique(SV.begin(), SV.end()) - SV.begin());
        V = SV.size(), E = n - 1;
        for (int i = 0; i < SV.size(); i++) {
            for (int j = 0; j+1 < n; j++) {
                if (onSeg(D[j], D[j+1], SV[i]) && SV[i] != D[j] && SV[i] != D[j+1])
                    E++;
            }
        }
//		printf("%d %d\n", E, V);
        int ret = E - V + 2; // V - E + F = 2, F = E - V + 2
        printf("Case %d: There are %d pieces.\n", ++cases, ret);
    }
    return 0;
}
/*
7 
1 1 1 5 2 1 2 5 5 1 3 5 1 1 
0
*/
Read More +
解題區/解題區 - UVa

UVa 1326 - Jurassic Remains

Problem

博物館對於骨頭化石進行拼湊作業，每一個骨頭上用 A - Z 去標記。兩片骨頭可以連接則表示具有相同的英文字母。

現在有數組骨頭，上面會有數個街口。現在找一組骨頭集合，使得每一個接口都有其連接的對象，盡可能使集合越大越好。

Sample Input

1
2
3
4
5
6
7
6
ABD
EG
GE
ABE
AC
BCD

Sample Output

1
2
5
1 2 3 5 6

Solution

題目相當於問找一個集合，使得每一個字母數量出現偶數次。

由於 N = 24，這個數量使用$O(2^{24})$ 相當消耗時間。使用中間相遇法 (在密碼學中可以見到，有點雙向 Bfs 的味道)，也就是分治算法的概念，將問題對切，從兩個統計結果中找交集。算法降至$O(2^{12} \times 12)$

考慮前 N/2 個骨頭 A、後 N/2 個骨頭 B，分別找到在字母集出現狀態為 S 的最佳解 A1, B1，若將兩個相同狀態組合$S \text{ XOR } S = 0$ 符合出現偶數次的條件。

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
#include <stdio.h> 
#include <string.h>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int main() {
    int n;
    char s[128];
    while (scanf("%d", &n) == 1) {
        int mask[32] = {};
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            int x = 0;
            for (int j = 0; s[j]; j++)
                x ^= (1<<(s[j] - 'A')); 
            mask[i] = x;
        }
        
        // D&C, dp, bitmask
        map<int, int> dp1, dp2;
        int div1 = n/2, div2 = n - n/2;
        for (int i = 0; i < (1<<div1); i++) {
            int x = 0;
            for (int j = 0; j < div1; j++) {
                if ((i>>j)&1)
                    x ^= mask[j];
            }
            if (dp1.count(x) || __builtin_popcount(dp1[x]) < __builtin_popcount(i))
                dp1[x] = i;			
        }
        for (int i = 0; i < (1<<div2); i++) {
            int x = 0;
            for (int j = 0; j < div2; j++) {
                if ((i>>j)&1)
                    x ^= mask[j + div1];
            }
            if (dp2.count(x) || __builtin_popcount(dp2[x]) < __builtin_popcount(i))
                dp2[x] = i;			
        }
        
        int retCnt = 0, retMask = 0;
        for (map<int, int>::iterator it = dp1.begin();
            it != dp1.end(); it++) {
            if (dp2.count(it->first)) {
                int x = it->second | ((dp2[it->first]) << div1);
                if (__builtin_popcount(x) > retCnt) {
                    retCnt = __builtin_popcount(x);
                    retMask = x;
                }
            }
        }
        printf("%d\n", retCnt);
        for (int i = 0, f = 0; i < n; i++) {
            if ((retMask>>i)&1) {
                if (f)	putchar(' ');
                f = 1;
                printf("%d", i+1);
            }
        }
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1105 - Coffee Central

Problem

給一個網格狀的地圖，每一個地點都有其相對應的人數，現在要建造一個咖啡廳，而咖啡廳所在位置可以引來在曼哈頓距離為 m 以內的所有網格上的人數。

對於每一組詢問，回報咖啡廳應該建在哪裡可以引來最多的人。

Sample Input

1
2
3
4
5
6
7
8
9
10
4 4 5 3
1 1
1 2
3 3
4 4
2 4
1
2 
4
0 0 0 0

Sample Output

1
2
3
4
Case 1:
3 (3,4)
4 (2,2)
5 (3,1)

Solution

由於單一組詢問數量不到 20，想必可以使用 O(n^2) 去應付每一組詢問。

窮舉每一個可能的位置，並且去計算該位置能引來多少的人。為了加速統計人數，曼哈頓距離內，是一個 45 度的正方形，紀錄上非常不方便。利用旋轉矩陣，將整個平面紀錄轉 45 度，讓每一次的區域統計變成平行於兩軸的區域，如此一來就可以在 O(1) 時間內找到區域總和。

特別小心答案為人數 0 時，答案輸出的座標。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN = 2048;
int sum[MAXN][MAXN];
void rotate(int x, int y, int &tx, int &ty, int dx, int dy) {
    tx = x - y + dy, ty = x + y;
}
void query(int limit, int dx, int dy) {
    int ret = 0, ret_x = 1, ret_y = 1;
    int tx, ty;
    for (int j = 1; j <= dy; j++) {
        for (int i = 1; i <= dx; i++) {
            rotate(i, j, tx, ty, dx, dy);
            int lx, rx, ly, ry, cnt;
            lx = max(tx - limit, 1);
            ly = max(ty - limit, 1);
            rx = min(tx + limit, dx + dy);
            ry = min(ty + limit, dx + dy);
            cnt = sum[rx][ry] - sum[rx][ly-1] - sum[lx-1][ry] + sum[lx-1][ly-1];
            if (cnt > ret) {
                ret = cnt, ret_x = i, ret_y = j;
            }
        }
    }
    printf("%d (%d,%d)\n", ret, ret_x, ret_y);
}
int main() {
    int dx, dy, n, q;
    int x, y, tx, ty, limit, cases = 0;
    while (scanf("%d %d %d %d", &dx, &dy, &n, &q) == 4 && dx) {
        // rotate matrix, rotate 45 degree
//		for (int i = 1; i <= dx; i++) {
//			for (int j = 1; j <= dy; j++) {
//				printf("(%d %d) -> (%d %d)\n", i, j, i - j + dy, i + j);
//			} 
//		}
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            rotate(x, y, tx, ty, dx, dy);
            sum[tx][ty]++;
        }
        
        for (int i = 1; i <= dx + dy; i++) {
            for (int j = 1, s = 0; j <= dx + dy; j++) {
                s += sum[i][j];
                sum[i][j] = sum[i-1][j] + s;
            }
        }
        
        printf("Case %d:\n", ++cases);
        for (int i = 0; i < q; i++) {
            scanf("%d", &limit);
            query(limit, dx, dy);
        }
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10476 - Spam or Not Spam

Problem

判斷訊息是否為垃圾訊息。

給數組垃圾訊息、非垃圾訊息，從中統計語言的出現頻率。例如 ABCDEFG 取 k-shingle 中 k = 3，那麼總共出現 ABC、BCD、CDE、DEF … 等。

接著按照題目給定的公式，計算輸入的訊息離垃圾訊息比較接近、還是非垃圾訊息。

n-gram 通常指的是以單詞 (word) 為切割單位，而 k-shingle 則是以字符 (char) 為切割單位。在巨量資料的開放課程中，以 shingle 去描述這樣的切割方式。

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
2 1 1
AAAA
BBBB CCCC
ENDMESSAGE
BBBB
ENDMESSAGE
AAAABBBB
ENDMESSAGE
AAABB
ENDMESSAGE
2 1 2
AAAA
BBBB CCCC
ENDMESSAGE
BBBB
ENDMESSAGE
AAAABBBB
ENDMESSAGE
AAABB
ENDMESSAGE
AAABB
ENDMESSAGE
0 0 0

Sample Output

1
2
3
4
5
6
7
8
Set 1:
0.21822 0.73030
non-spam
Set 2:
0.21822 0.73030
non-spam
0.21822 0.73030
non-spam

Solution

相當有趣的題目，終於把自然語言學習到的部分拿出來玩。但可惜題目沒有巨量資料那樣瘋狂，用 hash 去失真的操作，由於記憶體不夠，用 1-pass/2-pass 找 frequent items 之類的。

為了加速運算，改成 hash 會比較快，但只要一碰撞輸出機率時就會炸掉，所以還是別貿然嘗試。

特別用了 std::inner_product 來寫中間的數學運算，但仔細想想如果是兩個 std::map 要進行 std::inner_product() 仍然會因為元素不見得都會在兩個的 key set 而無法運作。std::inner_product 內建實作中只有單純的迭代，用在 vector 類型比較合適。

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
// NLP, n-gram, shingle
#include <stdio.h> 
#include <map>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <string.h>
using namespace std;
int map_product(pair<string, int> l, pair<string, int> r) {
    return l.second * r.second;
}
class Stat {
public:
    int kShingle;
    int sqsum;
    map<string, int> count;
    void init(int k) {
        kShingle = k, sqsum = 0;
        count.clear();
    }
    string toKey(string &s) { // retain for hash function
        return s;
    }
    void add(char s[]) {
        if (s[0] == '\0' || s[1] == '\0')	
            return;
        char end = '\0';
        for (int i = 2; s[i]; i++) {
            swap(s[i+1], end);
            string shingle = s+i-2;
            swap(s[i+1], end);
            count[toKey(shingle)] ++;
        }
    }
    void flush() {
        sqsum = inner_product(count.begin(), count.end(), count.begin(), 0,
           plus<int>(), map_product);
    }
    double distance(Stat &other) {
        double sum = 0;
        for (map<string, int>::iterator it = count.begin(), jt;
            it != count.end(); it++) {
            jt = other.count.find(it->first);
            if (jt != other.count.end()) {
                sum += it->second * jt->second;
            }
        }
        return (double) sum / sqrt((double) sqsum * other.sqsum);
    }
} spam, nonspam, msg;
const int MAXN = 1048576;
char buf[MAXN];
int main() {
    int cases = 0;
    int n, m, q;
    while (scanf("%d %d %d", &n, &m, &q) == 3 && n + m + q) {
        
        while (getchar() != '\n');
        spam.init(3), nonspam.init(3);
        
        for (int i = 0; i < n; i++) {
            while(gets(buf) && strcmp("ENDMESSAGE", buf))
                spam.add(buf);
        }
        for (int i = 0; i < m; i++) {
            while(gets(buf) && strcmp("ENDMESSAGE", buf))
                nonspam.add(buf);
        }
        spam.flush(), nonspam.flush();
            
        printf("Set %d:\n", ++cases);
        for (int i = 0; i < q; i++) {
            msg.init(3);
            while(gets(buf) && strcmp("ENDMESSAGE", buf))
                msg.add(buf);
            msg.flush();
            
            double spam_dist = msg.distance(spam);
            double nonspam_dist = msg.distance(nonspam);
            printf("%.5lf %.5lf\n", spam_dist, nonspam_dist);
            puts(spam_dist > nonspam_dist + 1e-10 ? "spam" : "non-spam");
        }
    }
    return 0;
}
/*
2 1 1
AAAA
BBBB CCCC
ENDMESSAGE
BBBB
ENDMESSAGE
AAAABBBB
ENDMESSAGE
AAABB
ENDMESSAGE
2 1 2
AAAA
BBBB CCCC
ENDMESSAGE
BBBB
ENDMESSAGE
AAAABBBB
ENDMESSAGE
AAABB
ENDMESSAGE
AAABB
ENDMESSAGE
0 0 0
*/
Read More +
解題區/解題區 - UVa

UVa 10498 - Happiness

Problem

每個人對於每種食材都有其滿意度，目標滿意度總和不超過上限。

準備一人份食材時，每單位的食材都各自有不同的花費，盡可能花最多的錢。

請問總共要花多少錢。

Sample Input

1
2
3
4
5
3 3
1 0.67 1.67
1 2 1 430
3 0 2 460
1 4 0 420

Sample Output

1
Nasa can spend 1354 taka.

Solution

每個人都花費相同的金額，因此把目標函數最大化後，乘上總人數即可。

現在要把問題轉換成線性規劃的模型，隨後套用 Simplex algorithm (單純形法)，可以參考 李宇骞《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》的簡報，概略說明模型的架構。資料網路上很多，不談論標準的處理程序。

接著閒聊自己的看法。

利用數形轉換的概念，從幾何概念下手，從三個變數來看，單純形法相當於在一個空間上，拿一個物體與平面找接觸，為了使目標函數最大化，會將物體表面的頂點帶入嘗試。

但是要將所有頂點找出來是相當消耗時間，因此爬行法可能會稍微好一點，也就是說，沿著物體表面，藉由一條邊爬行到更好位置上的頂點。由於線性約束，使得物體一定是凸多面體，在更高維度也是一樣的，不斷地爬升到更好的頂點後，最後一定會在最高點停止。

為了使爬行速度加快，每一次找爬升最多的鄰近點，相當於根據某一個約束，盡可能放大某一個維度上的變數 (有可能會將別的變數變小)，使得目標函數增加的值盡可能地多。根據原始的約束寫法，要找到計算仍然相當困難。

定義一個轉軸操作，讓整個問題的空間座標進行變換，方便撰寫。

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN = 64;
const int MAXM = 128;
const double eps = 1e-10, INF = 1e+30;
/*
	n: #variable
	m: #inequality constraint
	#inequality constraint format : \sum{a(j, i) xi} <= bj
	for all xi >= 0
 */
class Simplex {
public:
    int n, m;
    int N[MAXN], M[MAXM];
    double a[MAXM][MAXN], b[MAXM], c[MAXN];
    double xval[MAXN], z;
    void init(int n, int m) {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));
        memset(xval, 0, sizeof(xval));
        z = 0;
        this->n = n + m;
        this->m = m;
        
        for (int i = 0; i < m; i++)
            a[i][n+i] = 1;
        for (int i = 0; i < n; i++)
            N[i] = i;
        for (int i = 0; i < m; i++)
            M[i] = n + i;
    }
    int cmpZero(double v) {
        if (fabs(v) < eps)	return 0;
        return v < 0 ? -1 : 1;
    }
    void compute_xval() {
        for (int i = 0; i < n - m; i++) {
            xval[i] = 0;
            for (int j = 0; j < m; j++) {
                if (M[j] == i)
                    xval[i] = b[j];
            }
        }
    }
    void print() {
        printf("c ");
        for (int i = 0; i < n; i++)
            printf("%6.3lf ", c[i]);
        printf("%6.3lf\n", z);
        
        for (int i = 0; i < m; i++) {
            printf("a ");
            for (int j = 0; j < n; j++)
                printf("%6.3lf ", a[i][j]);
            printf("%6.3lf\n", b[i]);
        }
        puts("--");
        
        compute_xval();
        printf("x ");
        for (int i = 0; i < n - m; i++)
            printf("%6.3lf ", xval[i]);
        puts("");
    }
    void pivot(int row, int col) {
        double e = a[row][col];
        // normalization
        b[row] /= e;
        for (int i = 0; i < n; i++)
            a[row][i] /= e;
        // gaussian elimination
        for (int i = 0; i < m; i++) {
            if (i == row)
                continue;
            double t = a[i][col];
            b[i] = b[i] - t * b[row];
            for (int j = 0; j < n; j++)
                a[i][j] = a[i][j] - t * a[row][j];
        }
        z -= b[row] * c[col];
        
        double t = c[col];
        for (int i = 0; i < n; i++)
            c[i] = c[i] - t * a[row][i];
        swap(N[col], M[row]);
//        print();
    }
    void simplex() {
        double mx;
        int select_col, select_row, mn_row;
        // climb
        do {
            mx = -INF, select_col = select_row = mn_row = -1;
            for (int i = 0; i < n; i++) {
                if (cmpZero(c[i]) > 0) {
                    double mn = INF;
                    // find minmum increase with inequality constraint
                    for (int j = 0; j < m; j++) {
                        if (cmpZero(a[j][i]) > 0) {
                            if (b[j] / a[j][i] < mn)
                                mn = b[j] / a[j][i], mn_row = j;
                        }
                    }
                    // find maxmum climb with axis
                    if (mx < mn * c[i]) {
                        mx = mn * c[i];
                        select_col = i, select_row = mn_row;
                    }
                }
            }
            if (select_col != -1)
                pivot(select_row, select_col);
        } while (select_col != -1);
        
        compute_xval();
    }
} g;
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        g.init(n, m);
        
        for (int i = 0; i < n; i++)
            scanf("%lf", &g.c[i]);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++)
                scanf("%lf", &g.a[i][j]);
            scanf("%lf", &g.b[i]);
        }
        
        g.simplex();
        
//        for (int i = 0; i < n; i++) {
//            printf("x[%d] = %lf\n", i, g.xval[i]);
//        }
        printf("Nasa can spend %d taka.\n", (int) ceil(-g.z * m));
    }
    return 0;
}
/*
 Max x1 + 14*x2 + 6*x3
 s.t.
 x1 + x2 + x3 	<= 4
 x1              <= 2
 x3              <= 3
 3*x2   + x3     <= 6
 x1 , x2 , x3 , x4 , x5 , x6 , x7 >= 0
 
 3 4
 1 14 6
 1 1 1  4
 1 0 0  2
 0 0 1  3
 0 3 1  6
 
 2 2
 1 1
 2 1 12
 1 2 9
 
 2 2
 -1 -1
 2 1 12
 1 2 9
 
 3 3
 1 0.67 1.67
 1 2 1 430
 3 0 2 460
 1 4 0 420
 
 3 1
 30 10 20
 30 1 3 30
 
 3 3
 30 10 20
 30 1 3 30
 30 1 3 30
 30 1 3 30
 */
Read More +
手札日記

畢業典禮前的寧靜

門檻狀態

隨後去考這學期舉辦兩次的 多益測驗 ，沒想到面對這場考試心中是如此地平靜，沒有對選項的猶豫，刷新最低成績是有可能的 (目前 380 分)。這樣就不能畢業了呢！是啊。聽著「 你努力一下，肯定可以的！ 」「 你沒有比想像中的還差 」 … 諸如此類的說法。心中暗自竊笑，連同學拼英文字母都會分辨不出 a - z，這到底是有多笑話？

想到這一點，不知道接下來的日子要為什麼目標努力，就像被判斷有了癌症，日子已無多，那股挫折要往哪裡建立起信心。以前還能欺騙自己，要是往那裏發展，總會有所出路，別人肯定會需要我這種人，然而在即將到來的審判典禮，就像是要上死刑台面對廣場市民們的嘲笑、唾棄。現在正一步一步地接近 死刑台 ，由外傳來的喧鬧不斷地在陰暗的走廊上回響。

聽說以後找工作會被翻出來，主管可能看到這負面訊息就不會聘用了吧。俗話說的好，「水往低處流，人往低處走。」 希望是人給的，絕望也是 。

課程系列

在這一個多月中，寫個遊戲，做個美工。只為了一個課程的小作業，找一堆垃圾素材花了大半時間，設計出不少失敗的半成品，那也作罷，也看出能力也不過如此。

設計一個完整的遊戲是個不錯的經驗，以往都只有實作某個功能，沒有全方面地建造多分枝的架構。至於課程講述，不滿意課程教法，其一是浪費時間，其二是中英交雜，完全聽不懂在講什麼。教授隨口秀個英文，只有名詞也不明白到底想表達什麼，喝過洋墨水就比較厲害，也許只是他有他的上課方式，只是還沒去適應它。

資訊安全那門課，內容真的超有趣的，有數學、密碼、攻擊。內容比較淺，但樂趣還是在的。小考是炸了不少，已經到了不及格。那又如何呢？題目描述會錯意，答非所問，我還是感到樂趣無窮啊，這萌萌哒的學習樂此不彼！看不懂英文是給我懲罰，但也相對地學了不少新概念，不知道能不能多賺幾個 AC！

仇活動廚

為什麼突然講到 仇活動廚 ？其實這就跟仇女廚相同的性質，在大學生活中不乏有兩種極端的生存方式，其一是參與課外活動、其二是不斷地與作業奮戰。在最近會在 靠北中央 看到學弟們在 靠北參與活動 的人。如果仇活動廚多少因為曾經抱怨他們的文章，影響到系上的學弟深感抱歉，後來體悟得更多「 好不容易進到這所學校，卻找不到一起讀書的夥伴 」「 你們比我更強，為什麼只跑活動？ 」記得把接下來的話看完，先別急著罵我。

學弟這麼回應仇活動廚「學生個個不缺課、勤奮讀書、不互抄作業、 文武雙全、 不在考前翻考古題、 跑活動的個個拿書卷獎？」、「跑活動就腦袋空空？那你卷一了嗎？」

回過頭來看，一定有人善於跑活動，也會有人擅長靜靜地在角落讀書鑽研，從老爸那輩的人描述學習生活中，在照片也看得到它們一起在活動室閒聊、玩樂的照片，但也不少聽說他們一起讀書討論的心路歷程，但卻很少聽到這麼說以前同學，所以是仇恨被消磨、美化掉？還是本來就不存在這個原因？

來猜猜幾點可能性。

以前的課程若很少講求分組，是否有那段「 因為最近要跑活動，所以不能參與討論，沒時間去完成。 」那段心如刀割的話語肯定常常出沒在你我心中，分工合作要是變成 分功核作 ，除了 M 以外沒人願意一直接受這個事實，不是說每件事情都必須完成。既然有能力跑活動，肯定會有擅長的項目，即便那不是專業技術，那也是個值得敬重的能力。

即便是參與活動沒時間完成工作，那曾經扮演過 reviewer 嗎？將組員的努力審閱過一次，用自己理解的方式說一遍。但活動咖通常會冷嘲熱諷地說「 不過就這樣子吧？ 」這可是觸了禁忌，更不能說「 別組做得更好 」說好聽一點的話！更多的時候，等待的話語是「這樣理解沒錯吧」「那邊是不是可以作成 XX 的樣子 」「別組做得好，那我們有沒有辦法做得更好 」別忘記組員是自己人啊！你不是旁觀者，當被認為有能力不做事，給點意見、參與討論，討論的說法不只有一種，單一說法會讓人乏味，不斷地變換是 交流 、是 基友 。

像我這類看起來只會讀書，卻根本不會讀書的學生，冒牌下的存活者，多少有羨慕你們這些跑活動、讀書也有資質的人，在你們跑活動的時間，拿來做失敗的嘗試、痛苦的掙扎，累積能量 (讀作浪費時間去放鬆) 去衝刺一個失敗的嘗試 (在嘗試新的想法，必然需要新的刺激，墮落玩樂不是壞事，一昧地在同一個地方打轉，離開一陣子是好事)。就跟仇女風氣一樣，讀書的學生被跑活動的學生當作 工具人 ，拾人牙慧的態度讓人感到不愉快。萬一有人跳出來說「你自己選擇當工具人的！」「為什麼不跑活動？學到的內容也不少。」那試想過，如果這群人跟著跑活動，那他們還能在這所大學多久？在他們無法克服作業時，有人願意幫它們嗎？「 如果我不去做、讀的話，有人可以幫忙嗎？ 」

吾等非聖人，無法百分之百地做到自己講的內容。

近期心煩

聽說系館的樓梯都沒防護網，從最高層落下，能不能保證一定會死呢？畢業典禮那天，說著兒子要在今年上台大的爸媽將第一次看到就讀的環境，已經沒法畢業，要怎麼回應這份期待 … 想著想著，看來不用再煩惱這些了，一切都來不及了。當這樣想時，結局都已經定好，歷史紀錄使得一個人將無法正常化，勢必要排除在許多條件之外。既然已經不被認可、無法被認可，努力其他的條件只是要欺瞞自己。

在這大學四年裡，不斷地想要遇到一個欺騙我的人，即使是 謊言 也沒問題，讓我有點信心也好。放我一個人努力，在一旁相信我什麼的 … 太多這種人，失敗使我灰心喪智，不會相信你們。

Read More +
學校課程/資訊安全

資訊安全 Galois Fields C++ 軟體實作體驗

Problem

在 AES 中，利用 Galois fields$GF(2^{8})$ 為運算單位，有效地在 8-bits CPU 上高效地實作。

Galois Fields$GF(p^{n})$ 限定在質數 p 的 n 次方，便可存在有限的元素集合，支持加減乘除，同時可以利用 擴充歐幾里算法 得得到乘法反元素。從最簡單的 p = 2 開始看起，將 f(x) 視為一個元素。則

$$f(x) = a_{n-1}x^{n-1} + a_{n-2}x^{n-2} + ... + a_{1}x + a_{0} \\ a_{i} \in [0, p)$$

當 p = 2 時，f(x) 就跟一般的二進制數字儲存相同。當選定在 p 的 n 次方時，必須找一個 degree = n 的多項式，不被集合內的任何元素整除，來約束所有的運算保持在一個大小內。特別的是當 p = 2 時，加法和減法是等價運算 (在 p = 2 下，1 乘法反元素是自己本身)。

AES 取 8-bits 作為運算單位的用意很多，其一反元素可以在極小空間內儲存，可以用查表的方式得到。之所以選定 p = 2 的好處在於計算機的儲存架構，若在某些特殊硬體可以支持三進位的情況下，p = 3 則會比較有效率的使用，不然取用 p = 3 在二進制的電腦架構，需要轉換的儲存單位是很沒效率，並且覆蓋的集合大小也沒辦法全部使用。

GF 有什麼好處呢？其一的道理在於加解密設計要 防止線性關係 (線性代數太邪惡，很多種攻擊可以繞過線性關係的運算，拋開未知數也能求解)，對於 AES 的設計概念來說 GF 恰好符合這個條件。

AES

AES 選用$GF(2^{8})$，並且取$m(x) = x^8 + x^4 + x^3 + x + 1$ 作為模數，然後再設計一個以 GF 作為常數類型的多項式 Polynominal

$f(x) = s_{3}x^{3} + s_{2}x^{2} + s_{1}x + s_{0}$

每一個$s_{i}$ 都是一個 8-bits 的儲存單位，也就是說這個多項式是 32-bits 儲存。並且取用$m(x) = x^4 + 1$ 作為多項式的模數。AES 藉由 多項式相乘 ，將 4 個 8-bits 的資料交互影響產生出新的 4 個 8-bits，這在密碼學裡面造成 雪崩效應 。

跟之前講的一樣，GF 一定存在反操作，也就是乘法反元素，因此取用$03 x^{3} + 01 x^{2} + 01 x^{1} + 02$ 其乘法反元素為$0B x^{3} + 0D x^{2} + 09 x^{1} + 0E$。

接著，寫一個程式驗證反元素的計算吧！

備註：GF 裡面套用 GF 相當有趣，感覺可以無限擴充大小，當然任意質數也可以找反元素，但也只有 梅森質數 比較適合在電腦二進制系統中吧？

Sample Input

1
no input

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
00 01 8D F6 CB 52 7B D1 E8 4F 29 C0 B0 E1 E5 C7
74 B4 AA 4B 99 2B 60 5F 58 3F FD CC FF 40 EE B2
3A 6E 5A F1 55 4D A8 C9 C1 0A 98 15 30 44 A2 C2
2C 45 92 6C F3 39 66 42 F2 35 20 6F 77 BB 59 19
1D FE 37 67 2D 31 F5 69 A7 64 AB 13 54 25 E9 09
ED 5C 05 CA 4C 24 87 BF 18 3E 22 F0 51 EC 61 17
16 5E AF D3 49 A6 36 43 F4 47 91 DF 33 93 21 3B
79 B7 97 85 10 B5 BA 3C B6 70 D0 06 A1 FA 81 82
83 7E 7F 80 96 73 BE 56 9B 9E 95 D9 F7 02 B9 A4
DE 6A 32 6D D8 8A 84 72 2A 14 9F 88 F9 DC 89 9A
FB 7C 2E C3 8F B8 65 48 26 C8 12 4A CE E7 D2 62
0C E0 1F EF 11 75 78 71 A5 8E 76 3D BD BC 86 57
0B 28 2F A3 DA D4 E4 0F A9 27 53 04 1B FC AC E6
7A 07 AE 63 C5 DB E2 EA 94 8B C4 D5 9D F8 90 6B
B1 0D D6 EB C6 0E CF AD 08 4E D7 E3 5D 50 1E B3
5B 23 38 34 68 46 03 8C DD 9C 7D A0 CD 1A 41 1C
03 x^3 + 01 x^2 + 01 x^1 + 02 x^0
0B x^3 + 0D x^2 + 09 x^1 + 0E x^0
00 x^3 + 00 x^2 + 00 x^1 + 01 x^0
0B x^3 + 0D x^2 + 09 x^1 + 0E x^0

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
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
#include <stdio.h> 
#include <string.h>
// in AES, GF(2^8), m(x) = x^8 + x^4 + x^3 + x + 1
class GaloisField {
public:
    unsigned char v[32];
    int n;
    GaloisField() {
        n = 8;
        memset(v, 0, sizeof(v));
    }
    GaloisField(int val) {
        n = 8;
        memset(v, 0, sizeof(v));
        for (int i = 0; i < 8; i++)
            v[i] = (val>>i)&1;
    }
    GaloisField(const int a[], int an) {
        memset(v, 0, sizeof(v));
        n = 8;
        for (int i = 0; i <= an; i++)
            v[i] = a[i];
    }
    GaloisField operator+(const GaloisField &a) const {
        GaloisField r;
        for (int i = 0; i <= r.n; i++)
            r.v[i] = v[i] xor a.v[i];
        r.normal();
        return r;
    }
    GaloisField operator-(const GaloisField &a) const {
        return (*this) + a;
    }
    GaloisField operator*(const GaloisField &a) const {
        GaloisField r;
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= a.n; j++) 
                r.v[i+j] = r.v[i+j] xor (v[i] and a.v[j]);
        r.normal();
        return r;
    }
    GaloisField shift(int sn) const {
        GaloisField r;
        for (int i = 0; i < n; i++)
            r.v[i + sn] = v[i];
        return r;
    }
    bool operator<(const GaloisField &a) const {
        for (int i = 16; i >= 0; i--) {
            if (v[i] == 1 && a.v[i] == 1)
                return true;
            if (v[i] == 1 && a.v[i] == 0)
                return false;
            if (v[i] == 0 && a.v[i] == 1)
                return false;
        }
        return false;
    }
    GaloisField operator/(const GaloisField &a) const {
        for (int i = 16; i >= 0; i--) {
            if (a.v[i] == 1 && v[i] == 0)
                return GaloisField();
            if (a.v[i] == 0 && v[i] == 1)
                break;
        }
        GaloisField r, b = (*this), c;
        
        for (int i = n; i >= 0; i--) {
            c = a.shift(i);
            if (c < b) {
                r.v[i] = 1;
                for (int j = 16; j >= 0; j--)
                    b.v[j] = b.v[j] xor c.v[j];
            }
        }
        r.normal();
        return r;
    }
    GaloisField operator%(const GaloisField &a) const {
        GaloisField ret = (*this) - (*this) / a * a;
        return ret;
    }
    bool isZero() const {
        for (int i = 16; i >= 0; i--)
            if (v[i])	return 0;
        return 1;
    }
    GaloisField inverse() {
        const int m[] = {1, 1, 0, 1, 1, 0, 0, 0, 1}, mn = 8; // m(x) = x^8 + x^4 + x^3 + x + 1
        GaloisField y(m, mn);
        GaloisField g, a, b;
        
        exgcd((*this), y, g, a, b); // a x + b y = g
        return a;
    }
    void exgcd(GaloisField x, GaloisField y, GaloisField &g, GaloisField &a, GaloisField &b) {
        if (y.isZero()) {
            g = x, a = GaloisField(1), b = GaloisField(0);
        } else {
            exgcd(y, x%y, g, b, a), b = b - (x / y) * a;
        }
    }
    void normal() {
        const int m[] = {1, 1, 0, 1, 1, 0, 0, 0, 1}, mn = 8; // m(x) = x^8 + x^4 + x^3 + x + 1
        for (int i = 16; i - mn >= 0; i--) {
            if (v[i] == 1) {
                for (int j = mn, k = i; j >= 0; j--, k--)
                    v[k] = v[k] xor (m[j]);
            }
        }
    }
    void print() const {
        for (int i = 7; i >= 0; i--) {
            printf("%d", v[i]);
            if (i%4 == 0)	printf(" ");
        }
        puts("");
    }
    int getHbits() const {
        return v[7]<<3 | v[6]<<2 | v[5]<<1 | v[4];
    }
    int getLbits() const {
        return v[3]<<3 | v[2]<<2 | v[1]<<1 | v[0];
    }
};
void testGF() {
    int va[] = {1, 1, 1, 0, 1, 1, 0, 0};
    int vb[] = {0, 1, 0, 0, 0, 0, 1, 0};
    for (int i = 0; i < 256; i++) {
        GaloisField a(i);
        GaloisField b = a.inverse();
        printf("%X%X ", b.getHbits(), b.getLbits());
        if (i%16 == 15) puts("");
    }
}
class GF_Polynominal {
public:
    GaloisField v[32];
    int n;
    GF_Polynominal() {
        n = 4;
        for (int i = 0; i < 16; i++)
            v[i] = GaloisField();
    }
    GF_Polynominal(const GaloisField a[], int an) {
        n = 4;
        for (int i = 0; i <= an; i++)
            v[i] = a[i];
    }
    GF_Polynominal operator+(const GF_Polynominal &a) const {
        GF_Polynominal r;
        for (int i = 0; i <= r.n; i++)
            r.v[i] = v[i] + a.v[i];
        r.normal();
        return r;
    }
    GF_Polynominal operator-(const GF_Polynominal &a) const {
        return (*this) + a;
    }
    GF_Polynominal operator*(const GF_Polynominal &a) const {
        GF_Polynominal r;
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= a.n; j++) 
                r.v[i+j] = r.v[i+j] + (v[i] * a.v[j]);
        r.normal();
        return r;
    }
    GF_Polynominal shift(int sn) const {
        GF_Polynominal r;
        for (int i = 0; i < n; i++)
            r.v[i + sn] = v[i];
        return r;
    }
    bool operator<(const GF_Polynominal &a) const {
        for (int i = 8; i >= 0; i--) {
            if (!v[i].isZero() && !a.v[i].isZero())
                return true;
            if (v[i].isZero() != a.v[i].isZero())
                return false;
        }
        return false;
    }
    GF_Polynominal operator/(const GF_Polynominal &a) const {
        for (int i = 8; i >= 0; i--) {
            if (!a.v[i].isZero() && v[i].isZero())
                return GF_Polynominal();
            if (a.v[i].isZero() && !v[i].isZero())
                break;
        }
        GF_Polynominal r, b = (*this), c;
        
        for (int i = n; i >= 0; i--) {
            c = a.shift(i);
            if (c < b) {
                GaloisField t, x, y;
                for (int j = 16; j >= 0; j--) {
                    if (!c.v[j].isZero()) {
                        y = c.v[j], x = b.v[j];
                        break;
                    }
                }
                t = y.inverse() * x;
//				b.print();
//				c.print();
//				printf("gg %d\n", i);
//				y.print();
//				x.print();
//				y.inverse().print();
//				t.print();
                r.v[i] = t;
                for (int j = 8; j >= 0; j--)
                    b.v[j] = b.v[j] - c.v[j] * t;
            }
        }
//		printf("---> mod "); b.print();
//		puts("");
//		puts("div begin");
//		print();
//		a.print();
//		r.print();
//		(r * a).print();
//		(r * a + b).print();
//		puts("div end\n");
        r.normal();
        return r;
    }
    GF_Polynominal operator%(const GF_Polynominal &a) const {
        GF_Polynominal ret = (*this) - (*this) / a * a;
        return ret;
    }
    bool isZero() {
        for (int i = 8; i >= 0; i--)
            if (!v[i].isZero())	return 0;
        return 1;
    }
    GF_Polynominal inverse() {
        const GaloisField m[] = {GaloisField(1), GaloisField(0), GaloisField(0), GaloisField(0), GaloisField(1)};
        const int mn = 4; // m(x) = x^4 + 1
        GF_Polynominal y(m, mn);
        GF_Polynominal g, a, b;
        
        exgcd((*this), y, g, a, b); // a x + b y = g
        
        return a / g;
    }
    void exgcd(GF_Polynominal x, GF_Polynominal y, GF_Polynominal &g, GF_Polynominal &a, GF_Polynominal &b) {
//		puts("exgcd -----------------");
//		x.print();
//		y.print();
//		getchar();
        if (y.isZero()) {
            const GaloisField m1[] = {GaloisField(1)};
            const GaloisField m0[] = {GaloisField(0)};
            g = x, a = GF_Polynominal(m1, 1), b = GF_Polynominal(m0, 1);
            // a = g.inverse();
        } else {
            exgcd(y, x%y, g, b, a), b = b - (x / y) * a;
        }
    }
    void normal() {
        const GaloisField m[] = {GaloisField(1), GaloisField(0), GaloisField(0), GaloisField(0), GaloisField(1)};
        const int mn = 4; // m(x) = x^4 + 1
        for (int i = 16; i - mn >= 0; i--) {
            if (!v[i].isZero()) {
                GaloisField t = v[i];
                for (int j = mn, k = i; j >= 0; j--, k--)
                    v[k] = v[k] - (m[j] * t);
            }
        }
    }
    void print() const {
        for (int i = 3; i >= 0; i--) {
            printf("%X%X ", v[i].getHbits(), v[i].getLbits());
            printf("x^%d", i);
            if (i)	printf(" + ");
        }
        puts("");
    }
};
void testPoly() {
    const GaloisField m[] = {GaloisField(2), GaloisField(1), GaloisField(1), GaloisField(3)};
    const GaloisField m2[] = {GaloisField(14), GaloisField(9), GaloisField(13), GaloisField(11)};
    const int mn = 3, mn2 = 3;
    GF_Polynominal a(m, mn), b(m2, mn2);
    
    a.print();
    b.print();
    
    GF_Polynominal c = a * b;
    c.print();
    
    GF_Polynominal d = a.inverse();
    d.print();
}
int main() {
    testGF();
    testPoly();
    return 0;
}
Read More +
學校課程/資訊安全

資訊安全 小考筆記

Problem

  1. Follow

    1. What is a monoalphabetic cipher ?
    2. How large is the key space of the monoalphabetic cipher applied to English (just consider lower case letters) ?
    3. What is the main security weakness of a monoalphabetic cipher ?
    4. Please provide at least 4 approaches to prevent the above weakness.

  2. Block ciphers process messages in blocks like an extremely large substitution, but this is very difficult to implement for a very big block size. What is Shannon’s idea to realize a block cipher with big block size ?

  3. The S-box of DES round operation is not invertable, but why DES can decrypt ?

  4. Follow

    1. Please explain the OFB mode.
    2. In the OFB mode, we never reuse the same sequence (key+IV). If we reuse the key, then the attacker can recover message. Please describe very precisely (mathematiclly with symbols) how the attack works.

  5. Please compare the CFB mode the OFB mode by providing a table indicating at least 5 of their advantage and corresponding disadvantage.

  6. This question is about issues of random access of encryption and decryption. Define notations or symbols you need before providing your answer. Please describe how to use CFB mode and CTR mode to randomly encrypt and decrypt a file Why OFB mode is inappropriate to randomly encrypt and decrypt a file?

  7. Describe the details (as much as you remember) of AES operation and describe how efficiently implement AES on an 8-bit CPU ?

  8. How avalanche happens in AES within the first tow rounds ?

Notes

Part 1

monoalphabetic cipher 簡單來說比凱薩加密難一點，從每個字母都 shift 固定的數量來說，變成變動式的。換句話說就是單純的英文字母替換 (substitute)。由於要維持可逆的解密，替換必須符合一對一，所以方法數為 26! = 403291461126605635584000000。

但這種替換方式容易受到語言統計的攻擊，也就是說在英文的特性中，不是每個字母都出現相同的頻率，因為很多冗詞的使用，導致有些字母會特別多。也因此在找對應時，可以藉由這一個觀點，反向查找可能的替換，大幅度地降低搜索可能，讓解密變得相當容易。

為了解決這一語言統計的攻擊，可以藉由

  • 壓縮明文，破壞語言特性，但是壓縮算法有儲存的字典部分，仍可能發生字典結構被攻擊，進而進行解壓縮。
  • 增加垃圾字，撥點冗詞穿插在其中，把頻率不均的問題消彌。
  • 多個字符一起加密，相對於單一字母的替換，可以同時替換兩個以上，如 AA -> WT 之類的。
  • 使用多種替換，在不同時刻使用不同的替換表，同樣地可以把頻率問題解決。
  • 參照後續區段加密的一些技巧，如 CFB、OFB … 等，讓替換表進行變動。

Part 2

區段加密具有相當大的強度，當一次加密 64 bits 時，可以達到的對應種類高達 (2^64)!，沒有辦法將這種表格存放在記憶體，因為也要消耗 2^64 bits。

因此有 Shannon’s idea，利用 substitution (S-box)、permutation (P-box) 來完成對應，藉由 S-P 的組合，提供 混淆(confusion) 和 差異 (diffusion)。組合的效應遠比想像中的還大，儘管組合的方法數遠小於 (2^64)!，連兆分之一都不到，但簡單的概念可以在 64KB 記憶體大小內完成，效應上算相當划算。

Part 3

DES 的 S-box 屬於不可逆的操作 (8-bits to 6-bits)，然而 DES 在解密時，不需要將 S-box 往回推導，也就是不需要逆向操作，因為加密的 key 來自於 master key 和另一段的訊息 L(i) ，最後用 key 加密 R(i) 得到 L(i+1)。解密時，只需要將 R(i+1) (L(i) 會變成 S(i+1))帶入 S-box，就能重新產生出 key。

至於 DES 為什麼可以正確加解密，定義對於所有的任意明文 A, B，產生的密文 E(A) != E(B)。若明文差異在 L(i)，則在 R(i+1) 一定會不同。若明文差異在 R(i)，則在 key 相同，做 L(i+1) = R(i) XOR key 時，L(i+1) 也必定會不同。

Part 4

$$O_{i} = E_{k}(O_{i-1}); O_{-1} = IV \\ C_{i} = P_{i} \text{ XOR } O_{i}$$

為什麼 OFB 不能重新使用 key + IV 呢？原因是因為 已知明文攻擊 (Known plaintext attack) 。假設每一天都重新啟動，那麼攻擊者可以在事後得到密文對應的明文 (可能隔天才知道，儘管對應仍然是很難的)，那麼可以藉由數學概念來完成解密，無須考慮 key 是什麼內容。

$$C_{i} = P_{i} \text{ XOR } O_{i} \\ C_{j} = P_{j} \text{ XOR } O_{i} \\ C_{i} \text{ XOR } C_{j} = P_{i} \text{ XOR } P_{j}$$

假設 i 和 j 重複使用 key，那麼會發生已知密文$C_{i}, C_{j}$ (傳輸上一定會被發現) 和已知明文$P_{i}$，只要夾擊做 XOR，就可以直接得到$P_{j}$，當已知明文相當長時，竊取的效果就越好。

Part 5

比較 CFB 和 OFB。

特性\模式 CFB OFB
自同步 (self-synchronization) 可 不可
錯誤擴散 (error propagation) 有 無
預先計算 (preprocess key) 不可 可
隨機存取 (random access) 可 不可
資訊安全性 (message security) 高 低
  • 自同步 (self-synchronization) ，不用告知對方加密狀態，可以藉由數次的傳輸訊息，自動地將兩邊的狀態一致，在此之前會造成一段雜訊。斷線時，不必重複使用 IV 讓兩邊同步 (狀態相同時，才能正確解密)。
  • 錯誤擴散 (error propagation) ，也因為自同步的設計，導致在同步前都會有雜訊，或者在訊息被攻擊者竄改時，會影響該週期的狀態 ($C_{i-k}, C_{i-k+1}, ..., C_{i-1}$ )。
  • 預先計算 (preprocess key) ，預先計算 key 可以加快加解密速度，同時便可支持平行運算，這原因是因為 message-independent/dependent 之間的差異，狀態不依靠正在傳遞的訊息時，就可以預先處理。
  • 隨機存取 (random access) ，當要解析某個密文時，CFB 可以往前查找密文$C_{i-k}, C_{i-k+1}, ..., C_{i-1}$，得到當前的解密器所需要的狀態，放上 master key 就能進行解密。OFB 辦不到這一點，狀態不依賴訊息，那就要知道當前是哪個回合，從 IV 開始推導狀態，若密文在第 n 個位置，需要 O(n) 的時間來得到狀態，相對於 CFB 的 O(k) = O(1)來說相當耗時。
  • 資訊安全性 (message security) ，由於狀態與訊息獨立，會導致被攻擊者竄改內容時不易發現。在 CFB 中，由於依賴傳遞的訊息，當攻擊者竄改某個密文時會造成錯誤擴散，影響的解密時的明文不只一個，這也讓安全性提高。可以說是一體兩面的特性。

Part 6

  • CFB 狀態為 master key +$C_{i-k}, C_{i-k+1}, ..., C_{i-1}$
  • CTR 狀態為 master key + counter

CFB 解密某個密文時，往前查找密文即可解密。CTR 知道密文 offset 便可得到 counter。在獲得資訊上都是 O(k) 常數，因此支持隨機存取。

OFB 辦不到這一點，狀態不依賴訊息，那就要知道當前是哪個回合，從 IV 開始推導狀態，若密文在第 n 個位置，需要 O(n) 的時間來得到狀態，相對於 CFB 的 O(k) = O(1)來說相當耗時。

CFB 和 CTR 到底誰的隨機存取能力好呢？若檔案儲存會切割成數個，那 CFB 的隨機存取能力就更高一點。CTR 必須計算 offset，相較於 CFB 的紀錄架構會稍微地麻煩。

Part 7

AES 的計算結構都落在 GF(2^8)，一個 cell 的內容都是 GF(2^8)

  • substitue 需要 8-bits to 8-bits
  • shift rows 對於 8-bit 關聯不大 (移動記憶體的位置)
  • mixColume 上是 8-bits x 8-bits
  • add round key 對於每一個 cell XOR 8-bit keys

因此 AES 可以在 8-bits CPU 上有更好的實作效能，所需要的 clock cycle 會比較短。

Part 8

假設有兩個明文的 漢明距離 (Hamming distance) 為 1，在 128 bits 中有一個 1 bits 不同，意即$H(P, Q) = 1$。

Step\Round Round 1 Round 2
Substitue bytes 4 bits 16 bits
Shift rows 4 bits 16 bits
Mix Columes 16 bits 64 bits
Add Round key 16 bits 64 bits
  • 在 Substitue bytes 步驟時，S-box 會設計成期望當有一個 1-bits 不同，則替換出來的結果會有 4-bits 不同 (一個 cell 具有 8-bits。替換 8-bits 時，差異最少 0 bits、最多 8-bits，期望值是 4-bits)。
  • 在 Shift rows 步驟時，單純移動 cell 不影響差異。
  • 在 Mix Columes 步驟時，每一個 colume 會根據上一個 colume 的 4 個元素相互影響，因此會增加 4 倍。
  • 在 Add Round key 步驟時，由於 XOR 相同的 key，因此差異並不會改變。

最後，在 Round 2 時，能得到平均 64 bits 的差異。加密的明文一次 128 bits，差異期望值也就是一半的情況 64 bits，因此很快地就能達到期望的差異性。在隨後的 Round X 中，差異會在 64-bits 上下浮動都是有可能的。

Read More +
學校課程/介面設計

Game Maker 遊戲介面設計

前言

學校課程番外篇，有興趣者可以查閱 Github。

本文

本課程一開始著重 尼爾森法則 的介面設計，不只是在網頁操作等介面設計，雖然遊戲沒有複雜的狀態跟操作流程，但在設計上的操作反應、都應該要符合尼爾森法則。

Game Maker 這套軟體只是製作 UI 方便，遊戲性跟高難度設計不是很著重， 不看你的代碼或實作複雜度 。這也是本課程最弔詭的地方。Game Maker 有一個缺點，製作時的分工無法按照軟體分工的方式，實作部分代碼來完成，除非組員們都會寫 script 並且了解語法的變數存取方式。

從設計開始講起

可以從課程問卷中看到 link 幾個遵循的法則。

Visibility of system status

狀態可視有幾格要點，玩家方便知道當前狀態，例如所在關卡、遊戲模式的狀態、角色資訊的狀態、完成關卡的結算畫面 … 等。

紅框位置處表示狀態

同時在需要連續操作的完成流程，如銀行手續的設計，會顯示當前步驟進行到幾分之幾，來提示使用者其實還沒有完成所有步驟。然而在遊戲上，完成比例通常不是著重的一環，而是有哪關卡可以玩、有哪些關卡還沒去探訪過。

Match between system and the real world

主要為圖示運用，icon 對應的操作符合普遍性，通常會遇到的第一個錯誤設計是將原本用在某個地方的圖示拿來放在不應擺放的位置。例如音樂撥放器的撥放、暫停、停止、前轉、循環、 … 等，很容易在選擇上誤用箭頭的格式。

接著是在文字對應，選項的文字也要具有普遍性，符合直觀的反應文字，詞性也應選擇恰當 (當心誤用形容詞當選項文字)，問題描述的正面詢問與反面詢問，反應在選擇選項時應足夠明確 (反問內容是否合理，不常見的反面詢問應該捨棄，防止使用者用既有概念進行操作)。

遊戲規則設計符合合理，當要貼切真實世界時，如物理反應與遊戲元素之間的關聯應該符合，如遊戲中運用到水和火，兩物體若發生碰撞，反應結果應符合消滅對方的關係。

User control and freedom

所謂的自由度，玩家不會被困在一本道的遊戲設計，但是在抖 M 類型的遊戲中，只要一失敗就必須從頭打起。玩家不會一直被系統帶著跑，而無法中斷、暫停遊戲，同時也表明重新步入遊戲時，可以選擇自己進行的模式。

自由度的操控有很多，客製化玩家的操作、給予玩家改變遊戲的部分設計，如鍵盤控制的改變、允許玩家更動角色的樣貌、樣式，可以更動關卡模式，例如 L4D2 可以選擇專家模式 … 等。

Consistency and standards

一致性設計，相當於風格設計。

  • 按鈕的圖示在不同狀態若具有相同功能，使用圖示相同。
  • UI 擺放位置，不常因不同模式而更動 (突然放左、突然放右。)
  • 文字字型的使用統一使用，並且區分遊戲劇情與系統介面，相同類型的文字說明應符合一致。

Error prevention

防止錯誤操作，當玩家已經在別款遊戲中擅長使用快捷鍵時，那很有可能在遊戲中使用快捷鍵操作，這可能會造成不預期的反應，如快速關閉遊戲、啟動某個遊戲的系統功能。

因此在防止錯誤，通常會用 第二次詢問 來防止。在快捷操作上，二次詢問要利用不同的快捷鍵觸發，防止連按的快速操作，如連按兩次 ESC 突然跳出遊戲的蠢事。

提示操作的後果也是相當重要，必須在文字說明上明確描述，盡可能使用簡短的句子和例子來說明操作後果。說明時著重使用者觀點，而非功能性介紹 (介紹對於使用者的感受可能會變成怎麼樣，而不去說明電腦架構的效能 … 等專業知識)。

當遊戲需要高度複雜的邏輯，導致道具使用上的 順序性會影響流程 。當玩家處於無法通關的狀態時，提示哪個步驟錯誤，同時也告知玩家應該重新挑戰。這一類型就是引導提示。

Recognition rather than recall

在遊戲功能分類上，遊戲道具的使用類型應該設計主動操作與被動操作，在欄位劃分上是其中一種設計。當空間不足與進行欄位劃分，在道具的背景、顏色上的區分是一個解決方案，例如用三角形的外框表示消耗型道具、六角形表示永久的增益型道具。 用圖示背景與位置來區分操作類型 ，防範使用者如猴子般地等待道具效果。

Flexibility and efficiency of use

操作相當具有彈性跟有效地使用！

有些遊戲需要高度複雜的組合鍵來完成一個動作，同時也要求組合鍵的有效時間。先不論組合鍵的設計，若存在組合鍵，是否符合效率使用，是否可縮減成另一個指令，當分化深度歧異過大時，考量壓縮組合鍵的長度。例如有 5 個技能是由 3 個鍵組合觸發，4 個技能是由 5 個鍵組合觸發，壓縮到 4 個鍵以內 … 等。

正常情況下，有多少使用者會直觀這麼做，組合鍵設計是否合理，是否可以藉由 系統輔助來簡化操作流程 ？這些考量將成為易上手，入門玩家最需要的部分。就如 vim 編輯器的使用，直接面向高端使用者，入門就會相當地困難。

Aesthetic and minimalist design

提示、排版設計，在 Apple 軟體看得很明顯，操作相當簡單，不會一次把很多功能塞在同一個頁面。在功能性很強的軟體，常常會把很多參數調校放在同一個頁面，而沒有做好區別與預設，即使功能性很強、軟體很好用，但很多功能反而會被忽略，由於沒有好的簡化設計，第一手想要嘗試的使用者，會跳過好幾個功能設定進行反饋。 開發者開發的功能就白費了！

盡可能讓畫面簡潔，縮減不必要的進階資訊，用額外的方式體現，設計不同的介面模式。

Help users recognize, diagnose, and recover from errors

系統發生錯誤時，是否有足夠的資訊讓使用者查覺到 不是遊戲正常設定 ，來讓使用者回報這些程式設計 Bug。在系統設計的魯棒性，不應一個 Bug 產生而造成系統崩潰，遊戲也是一樣，讓使用者返回上一個正常的狀態，不會造成卡關、或者卡關之後遊戲損毀。

復原狀態對於小遊戲設計上相當困難啊！

Game

  • 故事劇情 (Storyline)
  • 遊戲性 (GamePlay)
  • 美學圖形 (Artistic/Graphics)
  • 音效特效 (Sound/Special effects)
  • 人工智慧 (AI)

故事劇情可以結合真實部分，在真假交織下發展。

可以參考 《额外加分 Extra Credits》 、 《TUN高品位低调宅》 系列影片，這將會告訴你遊戲如何設計才具有特色。

下面列了兩個影片，更多可以直接去觀看 youtube 上的頻道。

其他的列點就是一種個人價值觀體現，還沒有詳細學習。

Demo

影片加速展示內容。

Github

遊戲執行檔和開源代碼都在其中，當然還有遊戲的編輯器。更多的遊戲截圖在裡頭，只支持 windows 平台。

Read More +