解題區/解題區 - Zerojudge

b433. 中間相遇法

Problem

背景

加密的每一道過程若存在反運算，則存在解密的程序。絕對安全的加密沒有反運算，那解密也是沒有辦法做到的。通常加解密中一定會用到互斥或 (XOR) 運算，從表格來看，單獨看任何一行一列都恰好分配一半的 0、一半的 1。對於密碼來說，明文跟密文的關係，不管知道的明文還是密文的部分，猜中的機率只有 $1/2$，只要位元數一多，猜中的機率近乎 $(\frac{1}{2})^n \cong 0$。

「只用 XOR key 是不行的，再做一次不就回來了嗎？」

「那用循環位移和加法的 overflow 破壞線性結構！」

「但記得要能解密回來哦。」

於是某 M 提供一個簡單的加密運算，明文 $M$，加密金鑰 $key$

  • 密文 $C = ((M \text{<<<} key) + key) \text{ XOR } key$
  • 明文 $M = ((C \text{ XOR } key) + (\sim key) + 1) \text{>>>} key$

其中每一個運算都在 16-bit CPU 上運作，$\text{<<<}$ 表示循環左移 (circular shift)，$\sim$ 表示 1 補數。

用抽象化表示加解密流程

  • $C = E_{key}(M)$
  • $M = D_{key}(C)$

問題描述

現在某 M 正用他自己設計的加解密協定跟未來的自己溝通，但發現到這種加解密，如果對方知道某 M 一定會傳送哪一個明文，接著只要匹配密文，窮舉 $O(2^{16})$ 來找到加密金鑰就會破功。

在電影《模仿遊戲》中，德國納粹 Enigma 密碼機，訊息中的結尾一定會附加「希特勒萬歲！(Heil Hitler!)」匹配密文後，窮舉金鑰就能破解。而某 M 常常傳送「萌萌哒！(Moe Moe Ta!)」只需要 $O(2^{16})$ 就能被破解。

於是某 M 強化他的加密協定，希望破解者至少要在 $O(2^{32})$ 的時間內找到，拖延破解時間。

$C = E_{key_2}(E_{key_1}(M))$ $M = D_{key_1}(D_{key_2}(C))$

現在知道某 M 傳送的其中一組 $(C, M)$，請告訴某 M 有多少組 $(key_1, key_2)$ 的可能性。萬萬沒想到，中間相遇法能在 $O(2^{16} \times 16)$ 解決這個問題。

Sample Input

1
2
40380 23333
30767 13657

Sample Output

1
2
114688
45568

Solution

套用中間相遇法$E_{key_1}(M) = D_{key_2}(C)$ 分別對等式兩邊進行計算，查看相碰情況。

複雜度為窮舉所有可能的 $key_1$ 和 $key_2$，若用平衡樹進行碰撞檢查 $O(2^{16} \times 16)$，利用 HASH 可以降到 $O(2^{16})$，由於 $O(2^{16})$ 是記憶體可以宣告的，則直接使用數組來完成。

Hash

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
#include <bits/stdc++.h> 
using namespace std;
typedef unsigned short int UINT16;
class SimpleIdea {
public:
    UINT16 key;
    SimpleIdea(UINT16 k = 0):
        key(k) {}
    UINT16 encrypt(UINT16 m) {
        return (rotate_left(m, key&15) + key)^key;
    }
    UINT16 decrypt(UINT16 m) {
        return rotate_left((m^key)+(~key)+1, 16 - (key&15));
    }
private:
    UINT16 rotate_left(UINT16 x, UINT16 n) {
    	return  (x << n) | (x >> (16-n));
    }
} test;
int main() {
    int C, M;
    while (scanf("%d %d", &C, &M) == 2) {
        unordered_map<int, int> H1, H2;
        for (int i = 0; i < (1<<16); i++) {
            int key1 = i, key2 = i;
            test.key = key1;
            H1[test.encrypt(M)]++;
            test.key = key2;
            H2[test.decrypt(C)]++;
        }
        
        int ret = 0;
        for (auto &x : H1) {
            if (H2.count(x.first))
                ret += H2[x.first] * x.second;
        }
        printf("%d\n", ret);
    }
    return 0;
}

Array

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
#include <bits/stdc++.h> 
using namespace std;
typedef unsigned short int UINT16;
class SimpleIdea {
public:
    UINT16 key;
    SimpleIdea(UINT16 k = 0):
        key(k) {}
    UINT16 encrypt(UINT16 m) {
        return (rotate_left(m, key&15) + key)^key;
    }
    UINT16 decrypt(UINT16 m) {
        return rotate_left((m^key)+(~key)+1, 16 - (key&15));
    }
private:
    UINT16 rotate_left(UINT16 x, UINT16 n) {
    	return  (x << n) | (x >> (16-n));
    }
} test;
int main() {
    int C, M;
    while (scanf("%d %d", &C, &M) == 2) {
        int H[1<<16] = {}, ret = 0;
        for (int i = 0; i < (1<<16); i++) {
            test.key = i;
            H[test.encrypt(M)]++;
        }
        for (int i = 0; i < (1<<16); i++) {
            test.key = i;
            ret += H[test.decrypt(C)];
        }
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b428. 凱薩加密

Problem

背景

曾幾何時，基礎題庫已經成了不基礎的題庫。小小新手們寫個題目，不少拿了 TLE、CE 求助無門，就再也不想打開 Zerojudge。高中生哪有寫這麼困難的題目，高中生都不像高中生。在某 M 那個年代寫的題目非常簡單，沒有特別變化處理，更別說多麼高檔的資料結構，暴力算法 (naive algorithm) 就能輕鬆切題。

「年代變了呢，現在的高中生要寫出比大學生的某 M 更困難的題目」

重溫解題的那份初心吧！

題目描述

在西元前就存在的一種加密－凱薩加密為目前最早發現的替換加密 (substitution cipher)。其原理很簡單，將一段明文往替換成往後數的第 $k$ 個英文字母。

若用數學式表示凱薩加密和解密，如下：

加密 $C = E_K(P) = (P + k) \mod 26$
解密 $P = D_K(P) = (C - k) \mod 26$

例如 $k = 3$ 時，發生的情況如下：

明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表：DEFGHIJKLMNOPQRSTUVWXYZABC

從數學的觀點來看，每一個字母就是一個數字。

A = 0, B = 1, C = 2, …,X = 23, Y = 24, Z = 25

Sample Input

1
2
3
4
5
6
ABCDEFGHIJKLMNOPQRSTUVWXYZ 
DEFGHIJKLMNOPQRSTUVWXYZABC
DLQXABXEEQMEUQYLZPEK
YGLSVWSZZLHZPLTGUKZF
Z
Z

Sample Output

1
2
3
3
21
0

Solution

只需要看第一個字符的變換方式即可。

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
int main() {
    char s1[1024], s2[1024];
    while (scanf("%s %s", s1, s2) == 2)
        printf("%d\n", (((s2[0] - 'A') - (s1[0] - 'A'))%26 + 26)%26);
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

a761. 罐頭的記憶體

Problem

模擬作業系統的 dynamic memory allocation，

  • 宣告連續一段記憶體配置給某個程序，並且標記辨識碼。
  • 若宣告失敗，則輸出碰撞區域中，辨識碼最小的數字。
  • 詢問記憶體存取時，是否合法，若合法輸出程序的辨識碼。

Sample Input

1
2
3
4
5
6
7
8
7
load 29
map 1 25 39
map 2 23 24
map 3 22 25
map 4 25 40
store 33   
store 22

Sample Output

1
2
3
4
5
6
7
fail to load from 29
region 1 created
region 2 created
fail to create region 3, overlap with region 1
fail to create region 4, overlap with region 1
store region to 1
fail to store to 22

Solution

溫馨提示：此題的測資隨機，單純離散化套用二分查找，編號最小使用線性搜索即可通過。by 蔡神 asas

儘管直觀作法可以通過，來討論看看別種作法吧。

  • 線段樹 + 延遲標記 + 離線處理
    離散結果最多有 $O(N + Q)$ 的離散點，單筆操作複雜度為 $O(\log Q)$，空間複雜度 $O(Q)$，空間消耗量相較於其他算法最多 (附加延遲標記的使用)。
  • 分塊算法 + 離線處理
    利用分塊 Unrolled Linked List 的快取優勢來降複雜度，空間複雜度仍然是 $O(Q)$，單筆操作複雜度為 $O(\sqrt{Q})$。空間複雜度的常數比線段樹少一半以上，別忘詢問離線是共同的空間成本。
  • 分塊在線
    直接宣告 $O(2^{32})$ 進行配置，因此分塊大小為 $O(\sqrt{2^{32}})$。將配置連續區段用區間 $[l, r, pid]$ 的方式儲存在塊之中，用一個平衡樹維護每一個塊的狀態。由於要輸出編號最小的，詢問複雜度至少為 $O(65536)$，為了加速詢問可以利用剪枝 (塊的最小值仍大於當前的答案) 來完成。空間複雜度跟實際情況有關，這一做法在當前數據中是最快，記憶體最小的一種辦法，因為在線很多詢問點是沒必要實際存在的。

由於這一題沒有釋放記憶體操作，從均攤上可以清楚，分塊離線的修改離散點的次數最多為 $O(Q)$，也就是每一個點均被塗色僅僅一次，剩下就是在詢問上加速。

線段樹

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
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1<<21, INF = 0x3f3f3f3f;
class SegmentTree {
public:
    struct Node {
        int val, del;
        void init(int a = 0, int b = 0) {
            val = a, del = b;
        }
    } nodes[MAXN];
    void pushDown(int k, int l, int r) {
        if (nodes[k].del != INF) {
            nodes[k<<1].val = min(nodes[k<<1].val, nodes[k].del);
            nodes[k<<1].del = min(nodes[k<<1].del, nodes[k].del);
            nodes[k<<1|1].val = min(nodes[k<<1|1].val, nodes[k].del);
            nodes[k<<1|1].del = min(nodes[k<<1|1].del, nodes[k].del);
            nodes[k].del = INF;
        }
    }
    void pushUp(int k, int l, int r) {
        nodes[k].val = min(nodes[k<<1].val, nodes[k<<1|1].val);
    }
    void build(int k, int l, int r) { 
        nodes[k].init(INF, INF);
        if (l == r)	return ;
        int mid = (l + r)/2;
        build(k<<1, l, mid);
        build(k<<1|1, mid+1, r);
        pushUp(k, l, r);
    } 
    void assignUpdate(int k, int l, int r, int val) {
        nodes[k].del = min(nodes[k].del, val);
        nodes[k].val = min(nodes[k].val, val);
    }
    void assign(int k, int l, int r, int x, int y, int val) {
        if (x <= l && r <= y) {
            assignUpdate(k, l, r, val);
            return;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)	assign(k<<1, l, mid, x, y, val);
        if (y > mid)	assign(k<<1|1, mid+1, r, x, y, val);
        pushUp(k, l, r);
    }
    int query(int k, int l, int r, int x) {
        if (x <= l && r <= x || nodes[k].val == INF)
            return nodes[k].val;
        pushDown(k, l, r);
        int mid = (l + r)/2, ret;
        if (x <= mid)	ret = query(k<<1, l, mid, x);
        else			ret = query(k<<1|1, mid+1, r, x);
        pushUp(k, l, r);
        return ret;
    }
    int query(int k, int l, int r, int x, int y) {
        if (x <= l && r <= y || nodes[k].val == INF)
            return nodes[k].val;
        pushDown(k, l, r);
        int mid = (l + r)/2, ret = INF;
        if (x <= mid)
            ret = min(ret, query(k<<1, l, mid, x, y));
        if (y > mid)
            ret = min(ret, query(k<<1|1, mid+1, r, x, y));
        pushUp(k, l, r);
        return ret;
    }
} tree;
const int MAXQ = 524288;
char cmd[MAXQ][8];
int args[MAXQ][3];
int main() {
    int N;
    while (scanf("%d", &N) == 1) {
        map<int, int> R;
        for (int i = 0; i < N; i++) {
            scanf("%s", &cmd[i]);
            int a, b, c;
            if (cmd[i][0] == 'l')
                scanf("%d", &a), R[a] = 0;
            else if (cmd[i][0] == 'm')
                scanf("%d %d %d", &a, &b, &c), R[b] = R[c] = 0;
            else
                scanf("%d", &a), R[a] = 0;
            args[i][0] = a, args[i][1] = b, args[i][2] = c;
        }
        
        int size = 0;
        for (auto &x : R)
            x.second = ++size;
        tree.build(1, 1, size);
        for (int i = 0; i < N; i++) {
            int a, b, c, t;
            a = args[i][0], b = args[i][1], c = args[i][2];
            if (cmd[i][0] == 'l') {
                t = tree.query(1, 1, size, R[a]);
                if (t == INF)
                    printf("fail to load from %d\n", a);
                else
                    printf("load from region %d\n", t);
            } else if (cmd[i][0] == 'm') {
                t = tree.query(1, 1, size, R[b], R[c]);
                if (t != INF)
                    printf("fail to create region %d, overlap with region %d\n", a, t);
                else
                    printf("region %d created\n", a), tree.assign(1, 1, size, R[b], R[c], a);
            } else {
                t = tree.query(1, 1, size, R[a]);
                if (t == INF)
                    printf("fail to store to %d\n", a);
                else
                    printf("store to region %d\n", t);
            }
        }
    }
    return 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
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
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f, MAXQ = 524288;
class Unrolled {
public:
    int PILE, mask, shift;
    vector< vector<int> > nodes;
    vector<int> dirty;
    void alloc(int size) {
        nodes.clear(), dirty.clear();
        for (PILE = 1, shift = 0; PILE * PILE < size; PILE <<= 1, shift++);
        mask = PILE - 1;
        for (int l = 0, r; l < size; l = r+1) {
            r = min(l+PILE-1, size-1);
            nodes.push_back(vector<int>(r-l+1, INF));
            dirty.push_back(INF);
        }
    }
    int operator[](const int x) const {
        return nodes[x>>shift][x&mask];
    }
    int empty(int l, int r) {
        int bl = l>>shift, br = r>>shift;
        int ret = INF;
        if (bl == br) {
            for (int i = l; i <= r; i++)
                ret = min(ret, (*this)[i]);
            return ret;
        }
        for (int i = bl+1; i < br; i++)
            ret = min(ret, dirty[i]);
        for (int i = (bl+1) * PILE-1; i >= l; i--)
            ret = min(ret, (*this)[i]);
        for (int i = (br) * PILE; i <= r; i++)
            ret = min(ret, (*this)[i]);
        return ret;
    }
    void fill(int l, int r, int val) {
        int bl = l>>shift, br = r>>shift;
        for (int i = bl; i <= br; i++)
            dirty[i] = min(dirty[i], val);
        for (int i = l, bi; i <= r; i++)
            nodes[i>>shift][i&mask] = val;
    }
} mem;
char cmd[MAXQ][8];
int args[MAXQ][3];
int main() {
    int N;
    while (scanf("%d", &N) == 1) {
        map<int, int> R;
        for (int i = 0; i < N; i++) {
            scanf("%s", &cmd[i]);
            int a, b, c;
            if (cmd[i][0] == 'l')
                scanf("%d", &a), R[a] = 0;
            else if (cmd[i][0] == 'm')
                scanf("%d %d %d", &a, &b, &c), R[b] = R[c] = 0;
            else
                scanf("%d", &a), R[a] = 0;
            args[i][0] = a, args[i][1] = b, args[i][2] = c;
        }
        
        int size = 0;
        for (auto &x : R)
            x.second = size++;
        mem.alloc(size);
        for (int i = 0; i < N; i++) {
            int a, b, c, t;
            a = args[i][0], b = args[i][1], c = args[i][2];
            if (cmd[i][0] == 'l') {
                t = mem[R[a]];
                if (t == INF)
                    printf("fail to load from %d\n", a);
                else
                    printf("load from region %d\n", t);
            } else if (cmd[i][0] == 'm') {
                t = mem.empty(R[b], R[c]);
                if (t != INF)
                    printf("fail to create region %d, overlap with region %d\n", a, t);
                else
                    printf("region %d created\n", a), mem.fill(R[b], R[c], a);
            } else {
                t = mem[R[a]];
                if (t == INF)
                    printf("fail to store to %d\n", a);
                else
                    printf("store to region %d\n", t);
            }
        }
    }
    return 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
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 <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
class Unrolled {
public:
    struct Interval {
        long long l, r;
        int pid;
        Interval(long long a = 0, long long b = 0, int c = 0):
            l(a), r(b), pid(c) {}
        bool operator<(const Interval &x) const {
            return l < x.l || (l == x.l && r > x.r);
        }
        bool include(int x) const {
            return l <= x && x <= r;
        } 
    };
    long long PILE, mask;
    int shift;
    vector< set<Interval> > nodes;
    vector<int> dirty;
    void alloc(long long size) {
        nodes.clear(), dirty.clear();
        for (PILE = 1, shift = 0; PILE * PILE < size; PILE <<= 1, shift++);
        mask = PILE - 1;
        for (long long l = 0, r; l < size; l = r+1) {
            r = min(l+PILE-1, size-1);
            nodes.push_back(set<Interval>());
            dirty.push_back(INF);
        }
    }
    int operator[](const long long x) const {
        const set<Interval> &s = nodes[x>>shift];
        auto it = s.upper_bound(Interval(x, x));
        it = it == s.begin() ? it : --it;
        return it == s.end() || !(it->include(x)) ? INF : it->pid;
    }
    int empty(long long l, long long r) {
        int bl = l>>shift, br = r>>shift;
        int ret = INF;
        if (bl == br) {
            set<Interval> &s = nodes[bl];
            auto st = s.upper_bound(Interval(l, l));
            st = st == s.begin() ? st : --st;
            for (auto it = st; it != s.end(); it++) {
                if (max(l, it->l) <= min(r, it->r))
                    ret = min(ret, it->pid);
                if (it->l > r)
                    break;
            }
            return ret;
        }
        for (int i = bl+1; i < br; i++)
            ret = min(ret, dirty[i]);
        for (auto it = nodes[bl].rbegin(); it != nodes[bl].rend() && ret > dirty[bl]; it++) {
            if (max(l, it->l) <= min(r, it->r)) {
                ret = min(ret, it->pid);
            } else {
                break;
            }
        }
        for (auto it = nodes[br].begin(); it != nodes[br].end() && ret > dirty[br]; it++) {
            if (max(l, it->l) <= min(r, it->r)) {
                ret = min(ret, it->pid);
            } else {
                break;
            }
        }
        return ret;
    }
    void fill(long long l, long long r, int val) {
        int bl = l>>shift, br = r>>shift;
        for (int i = bl; i <= br; i++)
            dirty[i] = min(dirty[i], val);
        if (bl == br) {
            nodes[bl].insert(Interval(l, r, val));
            return ;
        }
        for (int i = bl+1; i < br; i++)
            nodes[i].insert(Interval(i*PILE, (i+1)*PILE-1, val));
        nodes[bl].insert(Interval(l, (bl+1) * PILE-1, val));
        nodes[br].insert(Interval(br*PILE, r, val));
    }
} mem;
int main() {
    int N;
    char cmd[8];
    while (scanf("%d", &N) == 1) {
        mem.alloc(1LL<<31);
        for (int i = 0; i < N; i++) {
            scanf("%s", &cmd);
            int a, b, c, t;
            if (cmd[0] == 'l') {
                scanf("%d", &a);
                t = mem[a];
                if (t == INF)
                    printf("fail to load from %d\n", a);
                else
                    printf("load from region %d\n", t);
            } else if (cmd[0] == 'm') {
                scanf("%d %d %d", &a, &b, &c);
                t = mem.empty(b, c);
                if (t != INF)
                    printf("fail to create region %d, overlap with region %d\n", a, t);
                else
                    printf("region %d created\n", a), mem.fill(b, c, a);
            } else {
                scanf("%d", &a);
                t = mem[a];
                if (t == INF)
                    printf("fail to store to %d\n", a);
                else
                    printf("store to region %d\n", t);
            }
        }
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b436. 圖片的梯度再進化

Problem

可以參考 中央大學影像處理實驗室 課程 講義第八章 邊擷取

除了索貝爾運算 Sobel operator，還有如 Prewitt operator、Kirsch operator … 等，來進行邊擷取。

Sample Input

1
2
3
2 2
0 0 0 255 255 255
255 255 255 255 255 255

Sample Output

1
2
3
2 2
191 191 191 128 128 128
128 128 128 64 64 64

Solution

比較麻煩是在處理邊緣擴充，寫一個函數去特判延伸的 pixel 位置。

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
#include <bits/stdc++.h> 
using namespace std;
class IMAGE {
public:
    struct Pixel {
        double r, g, b, a;
        Pixel(double x = 0, double y = 0, double z = 0, double w = 0):
            r(x), g(y), b(z), a(w) {}
        void read() {
            scanf("%lf %lf %lf", &r, &g, &b);
        }
        Pixel operator-(const Pixel &x) const {
        	return Pixel(r-x.r, g-x.g, b-x.b, a-x.a);
    	}
    	Pixel operator+(const Pixel &x) const {
        	return Pixel(r+x.r, g+x.g, b+x.b, a+x.a);
    	}
    	Pixel operator*(const double x) const {
        	return Pixel(r*x, g*x, b*x, a*x);
    	}
        Pixel operator/(const double x) const {
        	return Pixel(r/x, g/x, b/x, a/x);
    	}
    	void print() {
    		printf("%d %d %d", (int)round(r), (int)round(g), (int)round(b));
    	}
    };
    int W, H;
    static const int MAXN = 256;
    Pixel data[MAXN][MAXN], tmp[MAXN][MAXN];
    void read() {
        scanf("%d %d", &W, &H);
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j].read();
    }
    Pixel pabs(Pixel x) {
        return Pixel(fabs(x.r), fabs(x.g), fabs(x.b));
    }
    Pixel getPixel(int x, int y) {
        if (x >= 0 && y >= 0 && x < H && y < W)
            return data[x][y];
        if (y < 0)	return data[min(max(x, 0), H-1)][0];
        if (y >= W)	return data[min(max(x, 0), H-1)][W-1];
        if (x < 0)	return data[0][min(max(y, 0), W-1)];
        if (x >= H)	return data[H-1][min(max(y, 0), W-1)];
        return Pixel(0, 0, 0);
    }
    void border() {
        const int dx[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
        const int dy[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
        const int xw[] = {-1, 0, 1, -2, 0, 2, -1, 0, 1};
        const int yw[] = {-1, -2, -1, 0, 0, 0, 1, 2, 1};
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                Pixel Dx(0, 0, 0), Dy(0, 0, 0);
                for (int k = 0; k < 9; k++) {
                    Dx = Dx + getPixel(i+dx[k], j+dy[k]) * xw[k];
                    Dy = Dy + getPixel(i+dx[k], j+dy[k]) * yw[k];
                }
                Dx = pabs(Dx), Dy = pabs(Dy);
                tmp[i][j] = (Dx + Dy)/8.0;
            }
        }
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j] = tmp[i][j];
    }
    void print() {
        printf("%d %d\n", W, H);
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j].print(), printf("%c", j == W-1 ? '\n' : ' ');
    }
} test;
int main() {
    test.read();
    test.border();
    test.print();
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b434. 圖片的梯度

Problem

可以參考 中央大學影像處理實驗室 課程 講義第八章 邊擷取

邊緣擷取可以靠相鄰像素的差異來判斷是否是邊緣，若顏色差異很大則表示是邊。然而圖片像素是不連續的離散點，因此沒有辦法利用微積分學到的微分來得精準，而是要採用差分 (減法)，至於遮罩要取多大是個問題，一般而言還會搭配降噪的矩陣來完成。

如 Prewitt operator、Sobel operator、Kirsch operator … 等，矩陣都有搭配降噪處理。之所以用矩陣表示，是為了讓 GPU 快速地計算數值。

Sample Input

1
2
3
2 2
0 0 0 255 255 255
255 255 255 255 255 255

Sample Output

1
2
3
2 2
255 255 255 0 0 0
0 0 0 0 0 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
#include <bits/stdc++.h> 
using namespace std;
class IMAGE {
public:
    struct Pixel {
        double r, g, b, a;
        Pixel(double x = 0, double y = 0, double z = 0, double w = 0):
            r(x), g(y), b(z), a(w) {}
        void read() {
            scanf("%lf %lf %lf", &r, &g, &b);
        }
        Pixel operator-(const Pixel &x) const {
        	return Pixel(r-x.r, g-x.g, b-x.b, a-x.a);
    	}
    	Pixel operator+(const Pixel &x) const {
        	return Pixel(r+x.r, g+x.g, b+x.b, a+x.a);
    	}
    	Pixel operator*(const double x) const {
        	return Pixel(r*x, g*x, b*x, a*x);
    	}
        Pixel operator/(const double x) const {
        	return Pixel(r/x, g/x, b/x, a/x);
    	}
    	void print() {
    		printf("%d %d %d", (int)round(r), (int)round(g), (int)round(b));
    	}
    };
    int W, H;
    static const int MAXN = 256;
    Pixel data[MAXN][MAXN];
    void read() {
        scanf("%d %d", &W, &H);
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j].read();
    }
    Pixel pabs(Pixel x) {
        return Pixel(fabs(x.r), fabs(x.g), fabs(x.b));
    }
    void border() {
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                Pixel dx(0, 0, 0), dy(0, 0, 0);
                if (i+1 < H)
                    dx = data[i+1][j] - data[i][j];
                if (j+1 < W)
                    dy = data[i][j+1] - data[i][j];
                dx = pabs(dx), dy = pabs(dy);
                data[i][j] = (dx + dy)/2.0;
            }
        }
    }
    void print() {
        printf("%d %d\n", W, H);
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j].print(), printf("%c", j == W-1 ? '\n' : ' ');
    }
} test;
int main() {
    test.read();
    test.border();
    test.print();
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b427. 漸層色彩

Problem

給予兩個顏色的像素，在一張空白影像中使用漸層效果。

  • 水平由左到右的漸層
  • 從中心點擴散的漸層

Sample Input

1
3 3 0 0 0 0 255 255 255 255 255

Sample Output

1
2
3
4
3 3
0 0 0 255 128 128 128 255 255 255 255 255
0 0 0 255 128 128 128 255 255 255 255 255
0 0 0 255 128 128 128 255 255 255 255 255

Solution

線性內插，特別小心中心點 (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
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h> 
using namespace std;
class IMAGE {
public:
    struct Pixel {
        double r, g, b, a;
        Pixel(double x = 0, double y = 0, double z = 0, double w = 0):
            r(x), g(y), b(z), a(w) {}
        void read() {
            scanf("%lf %lf %lf %lf", &r, &g, &b, &a);
        }
        Pixel operator-(const Pixel &x) const {
        	return Pixel(r-x.r, g-x.g, b-x.b, a-x.a);
    	}
    	Pixel operator+(const Pixel &x) const {
        	return Pixel(r+x.r, g+x.g, b+x.b, a+x.a);
    	}
    	Pixel operator*(const double x) const {
        	return Pixel(r*x, g*x, b*x, a*x);
    	}
        Pixel operator/(const double x) const {
        	return Pixel(r/x, g/x, b/x, a/x);
    	}
    	void print() {
    		printf("%d %d %d %d", (int)round(r), (int)round(g), (int)round(b), (int)round(a));
    	}
    };
    int W, H;
    static const int MAXN = 300;
    Pixel data[MAXN][MAXN];
    void read() {
        scanf("%d %d", &W, &H);
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j].read();
    }
    void alloc() {
        int TYPE;
        Pixel st, ed;
        scanf("%d %d %d", &W, &H, &TYPE);
        st.read(), ed.read();
        gradient(st, ed, TYPE);
    }
    void gradient(Pixel st, Pixel ed, int TYPE) {
        if (TYPE != 0 && TYPE != 1)
            return;
        if (TYPE == 0) {
            for (int i = 0; i < H; i++)
                for (int j = 0; j < W; j++) 
                    data[i][j] = W-1 ? st + (ed - st) * j / (W-1) : st;
        } else {
            double cx = (H-1)/2.0, cy = (W-1)/2.0;
            double cr = hypot(cx, cy);
            for (int i = 0; i < H; i++)
                for (int j = 0; j < W; j++)
                    data[i][j] = cr ? st + (ed - st) * hypot(i-cx, j-cy) / cr : st;
        }
    }
    void print() {
        printf("%d %d\n", W, H);
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j].print(), printf("%c", j == W-1 ? '\n' : ' ');
    }
} test;
int main() {
    test.alloc();
    test.print();
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b426. 宇宙光明體

Problem

模擬兩張圖片的合成。

將前景圖片疊在背景圖片之上，按照權重比例來融合重疊部分得像素。

Sample Input

1
2
3
4
5
0 0 0.5
1 1
255 255 255
1 1
0 0 0

Sample Output

1
2
1 1
128 128 128

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
#include <bits/stdc++.h> 
using namespace std;
const double eps = 0;
class IMAGE {
public:
    struct Pixel {
        long double r, g, b, a;
        Pixel(long double x = 0, long double y = 0, long double z = 0, long double w = 0):
            r(x), g(y), b(z), a(w) {}
        void read() {
            int p1, p2, p3;
            scanf("%d %d %d", &p1, &p2, &p3);
            r = p1, g = p2, b = p3;
        }
        Pixel operator-(const Pixel &x) const {
        	return Pixel(r-x.r, g-x.g, b-x.b, a-x.a);
    	}
    	Pixel operator+(const Pixel &x) const {
        	return Pixel(r+x.r, g+x.g, b+x.b, a+x.a);
    	}
    	Pixel operator*(const long double x) const {
        	return Pixel(r*x, g*x, b*x, a*x);
    	}
        Pixel operator/(const long double x) const {
        	return Pixel(r/x, g/x, b/x, a/x);
    	}
    	void print() {
    		double p1 = r, p2 = g, p3 = b, p4 = a;
    		printf("%.0lf %.0lf %.0lf", p1 + eps, p2 + eps, p3 + eps);
    	}
    };
    int W, H;
    static const int MAXN = 256;
    Pixel data[MAXN][MAXN];
    void read() {
        scanf("%d %d", &W, &H);
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j].read();
    }	
    void add(IMAGE &other, int X, int Y, double OPACITY) {
        for (int i = 0; i < other.H && i+X < H; i++) {
            for (int j = 0; j < other.W && j+Y < W; j++) {
                if (i+X >= 0 && j+Y >= 0)
                    data[i+X][j+Y] = other.data[i][j] * OPACITY + data[i+X][j+Y] * (1 - OPACITY);
            }
        }
    }
    void print() {
        printf("%d %d\n", W, H);
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j].print(), printf("%c", j == W-1 ? '\n' : ' ');
    }
} back, fore;
int main() {
    double OPACITY;
    int X, Y;
    scanf("%d %d %lf", &X, &Y, &OPACITY);
    fore.read();
    back.read();
    back.add(fore, Y, X, OPACITY);
    back.print();
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b425. 抽菸動作 請勿模仿

Problem

替影像打上馬賽克效果，馬賽克效果是把區域內部的每一個像素改變，改變的方法為從舊的圖像中，搜索以其為中心的 11 x 11 方形內部所有像素的平均。

這一題要馬賽克區域為圓形，接著找到方形內部的像素平均即可。

Sample Input

1
2
3
4
0 1 2
1 2
1 2 3
4 5 6

Sample Output

1
2
3
1 2
3 4 5
3 4 5

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
#include <bits/stdc++.h> 
using namespace std;
class IMAGE {
public:
    struct Pixel {
        double r, g, b, a;
        Pixel(double x = 0, double y = 0, double z = 0, double w = 0):
            r(x), g(y), b(z), a(w) {}
        void read() {
            scanf("%lf %lf %lf", &r, &g, &b);
        }
        Pixel operator-(const Pixel &x) const {
        	return Pixel(r-x.r, g-x.g, b-x.b, a-x.a);
    	}
    	Pixel operator+(const Pixel &x) const {
        	return Pixel(r+x.r, g+x.g, b+x.b, a+x.a);
    	}
    	Pixel operator*(const double x) const {
        	return Pixel(r*x, g*x, b*x, a*x);
    	}
        Pixel operator/(const double x) const {
        	return Pixel(r/x, g/x, b/x, a/x);
    	}
    	void print() {
    		printf("%d %d %d", (int)round(r), (int)round(g), (int)round(b));
    	}
    };
    int W, H;
    static const int MAXN = 300;
    Pixel data[MAXN][MAXN], tmp[MAXN][MAXN];
    void read() {
        scanf("%d %d", &W, &H);
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j].read();
    }
    void blur(long long X, long long Y, long long R) {
        if (R < 0)	return ;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if ((i-X)*(i-X) + (j-Y)*(j-Y) <= R*R) {
                    Pixel B(0, 0, 0);
                    int cnt = 0;
                    for (int a = -5; a <= 5; a++) {
                        for (int b = -5; b <= 5; b++) {
                            if (i+a < H && j+b < W && i+a >= 0 && j+b >= 0) {
                                B = B + data[i+a][j+b];
                                cnt++;
                            }
                        }
                    }
                    tmp[i][j] = B / cnt;
                } else {
                    tmp[i][j] = data[i][j];
                }
            }
        }
        
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j] = tmp[i][j];
    }
    void print() {
        printf("%d %d\n", W, H);
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j].print(), printf("%c", j == W-1 ? '\n' : ' ');
    }
} test;
int main() {
    long long X, Y, R;
    scanf("%lld %lld %lld", &X, &Y, &R);
    test.read();
    test.blur(Y, X, R);
    test.print();
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b424. 圖片縮放

Problem

此題有精準度誤差，未能提交成功。

進行圖片縮放，有兩種方案來補足缺失或者是簡化的像素計算。不管縮放如何，在新的坐標系的點可以對應到舊坐標系中，並且會有四個像素點 (正方形) 包含這個對應點，有可能會有所缺失，但至少包含一個點。

  • 最近鄰點法 (nearest-neighbor approach)
    找正方形中哪個點最靠近新的對應點，就令其像素顏色等於最靠近的點。
  • 雙線性內插 (bi-linear interpolation)
    顏色由相鄰四個點決定，使用雙性內插來得到新的像素顏色。

特別注意，雖然邊長根據縮放四捨五入，但在計算時先不考慮最終結果的長寬，否則縮放倍率也會跟著四捨五入。

可以參考 中央大學影像處理實驗室 課程 講義第二章

Sample Input

1
2
3
2 2 0
2 1 
1 2 3 255 4 5 6 255

Sample Output

1
2
3
4 2
1 2 3 255 3 4 5 255 4 5 6 255 4 5 6 255
1 2 3 255 3 4 5 255 4 5 6 255 4 5 6 255

Solution

除了陷阱的邊長四捨五入外，精準度根據雙性內插影響。

雙線性內插可以由下列兩種方案，或者還有其他的

  • 兩次 lerp 插值，先水平後垂直或者先垂直後水平
  • 特別的 $f(x, y) = (1-a)(1-b) g(j, k) + a(1-b) g(j+1, k) + (1-a) b g(j, k+1) + a b g(j+1, k+1)$

特別發現到，第二種方案沒有用到除法運算，但乘法運算的優先順序會影響到誤差。然而我的代碼是混用造成難以評估的誤差。關於第二種方案的坐標系，可以參考講義中的圖示。

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 <bits/stdc++.h> 
using namespace std;
const double eps = 1e-18;
class IMAGE {
public:
    struct Pixel {
        long double r, g, b, a;
        Pixel(long double x = 0, long double y = 0, long double z = 0, long double w = 0):
            r(x), g(y), b(z), a(w) {}
        void read() {
            int p1, p2, p3, p4;
            scanf("%d %d %d %d", &p1, &p2, &p3, &p4);
            r = p1, g = p2, b = p3, a = p4;
        }
        Pixel operator-(const Pixel &x) const {
        	return Pixel(r-x.r, g-x.g, b-x.b, a-x.a);
    	}
    	Pixel operator+(const Pixel &x) const {
        	return Pixel(r+x.r, g+x.g, b+x.b, a+x.a);
    	}
    	Pixel operator*(const long double x) const {
        	return Pixel(r*x, g*x, b*x, a*x);
    	}
        Pixel operator/(const long double x) const {
        	return Pixel(r/x, g/x, b/x, a/x);
    	}
    	void print() {
    		double p1 = r, p2 = g, p3 = b, p4 = a;
    		printf("%.0lf %.0lf %.0lf %.0lf", p1 + eps, p2 + eps, p3 + eps, p4 + eps);
    	}
    };
    int W, H;
    static const int MAXN = 512;
    Pixel data[MAXN][MAXN], tmp[MAXN][MAXN];
    void read() {
        scanf("%d %d", &W, &H);
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j].read();
    }
    int isValid(int x, int y) {
        return x >= 0 && y >= 0 && x < H && y < W;
    }
    void resize(long double SX, long double SY, int trans = 0) {
        if (trans != 0 && trans != 1)
            return ;			
        int rW = (int) round(SX * W);
        int rH = (int) round(SY * H);
        if (rW > 256 || rH > 256 || rW <= 0 || rH <= 0)
            return ;
        for (int i = 0; i < rH; i++) {
            for (int j = 0; j < rW; j++) {
                long double x = i / SY;
                long double y = j / SX;
                int lx, rx, ly, ry;
                lx = floor(x), rx = ceil(x);
                ly = floor(y), ry = ceil(y);
                
                Pixel v[] = {data[lx][ly], data[lx][ry], data[rx][ly], data[rx][ry]};
                int px[] = {lx, lx, rx, rx};
                int py[] = {ly, ry, ly, ry};
                if (trans == 0) {
                    Pixel t1, t2;
                    if (isValid(px[0], py[0]) && isValid(px[1], py[1]) && isValid(px[2], py[2]) && isValid(px[3], py[3])) {
                        long double a = x - lx, b = y - ly;
                        tmp[i][j] = v[0] * (1 - a) * (1 - b) + v[2] * a * (1 - b)
                                    + v[1] * (1 - a) * b + v[3] * a * b;
                    } else if (isValid(px[0], py[0]) && isValid(px[2], py[2])) {
                        if (rx != lx)
                            tmp[i][j] = v[0] + (v[2] - v[0]) * ((x - lx) / (rx - lx));
                        else
                            tmp[i][j] = v[0];
                    } else if (isValid(px[0], py[0]) && isValid(px[1], py[1])) {
                        if (ry != ly)
                            tmp[i][j] = v[0] + (v[1] - v[0]) * ((y - ly) / (ry - ly));
                        else
                            tmp[i][j] = v[0];
                    } else if (isValid(px[0], py[0])) {
                        tmp[i][j] = v[0];
                    } else {
                        puts("WTF");
                    }
                } else {
                    int c = -1;
                    double mndist;
                    for (int k = 0; k < 4; k++) {
                        if (!isValid(px[k], py[k]))
                            continue;
                        double d = (x-px[k])*(x-px[k])+(y-py[k])*(y-py[k]);
                        if (c == -1 || mndist > d)
                            c = k, mndist = d;
                    }
                    tmp[i][j] = data[px[c]][py[c]];
                }
            }
        }
        W = rW, H = rH;
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j] = tmp[i][j];
    }
    void print() {
        printf("%d %d\n", W, H);
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                data[i][j].print(), printf("%c", j == W-1 ? '\n' : ' ');
    }
} test;
int main() {
    double X, Y;
    int TYPE;
    scanf("%lf %lf %d", &X, &Y, &TYPE);
    test.read();
    test.resize(X, Y, TYPE);
    test.print();
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b423. 魔術橡皮擦

Problem

提供影像去背、相鄰去色兩種方案。

  • 去背對整張影像找像素差小於某一個範圍內，就將其 alpha 值設成 0。
  • 相鄰去色對鄰近四個方向上下左右進行搜索，將像素差低於某個閥值的都加入到集合中進行 alpha 值設成 0。

Sample Input

1
2
3
4
0 0 0 0
3 2
1 2 3 255 4 5 6 255 7 8 9 255
10 11 12 255 13 14 15 255 16 17 18 255

Sample Output

1
2
3
3 2
1 2 3 0 4 5 6 255 7 8 9 255
10 11 12 255 13 14 15 255 16 17 18 255

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
#include <bits/stdc++.h>
using namespace std;
int X, Y, TYPE, DIFF;
namespace Image {
    const int MAXN = 256;
    int n, m, rgba[MAXN][MAXN][4], used[MAXN][MAXN] = {};
    int RGB_diff(int x, int y, int a, int b) {
        return (rgba[x][y][0]-rgba[a][b][0])*(rgba[x][y][0]-rgba[a][b][0])+
                (rgba[x][y][1]-rgba[a][b][1])*(rgba[x][y][1]-rgba[a][b][1])+
                (rgba[x][y][2]-rgba[a][b][2])*(rgba[x][y][2]-rgba[a][b][2]);
    }
    void gTransparent(int x, int y, long long diff) {
        if (x < 0 || y < 0 || x >= m || y >= n || diff < 0)
            return ;
        diff = diff * diff;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (RGB_diff(x, y, i, j) <= diff)
                    rgba[i][j][3] = 0;
    }
    void lTransparent(int x, int y, int ox, int oy, long long diff) {
        if (ox < 0 || oy < 0 || ox >= m || oy >= n || diff < 0)
            return ;
        static const int dx[] = {0, 0, 1, -1};
        static const int dy[] = {1, -1, 0, 0};
        if (x < 0 || y < 0 || x >= m || y >= n)
            return ;
        if (RGB_diff(x, y, ox, oy) > diff * diff || used[x][y])
            return ;
        rgba[x][y][3] = 0, used[x][y] = 1;
        for (int i = 0; i < 4; i++)
            lTransparent(x+dx[i], y+dy[i], ox, oy, diff);
    }
    void print() {
        printf("%d %d\n", n, m);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++)
                printf("%d %d %d %d%c", rgba[i][j][0], rgba[i][j][1], rgba[i][j][2], rgba[i][j][3], j == n-1 ? '\n' : ' ');
        }
    }
}
int main() {
    scanf("%d %d %d %d", &X, &Y, &TYPE, &DIFF);
    scanf("%d %d", &Image::n, &Image::m);
    for (int i = 0; i < Image::m; i++)
        for (int j = 0; j < Image::n; j++)
            for (int k = 0; k < 4; k++)
                scanf("%d", &Image::rgba[i][j][k]);
    swap(X, Y);
    if (TYPE == 0)
        Image::gTransparent(X, Y, DIFF);
    if (TYPE == 1)
        Image::lTransparent(X, Y, X, Y, DIFF);
    Image::print();
    return 0;
}
Read More +