# APCS實作題2022年6月第2題：字串解碼

> 日期：2023年9月23日
> 作者：王一哲
> 題目來源：111年6月實作題第2題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=i400)

<br />

## 題目

### 問題描述

有一個字串加密系統，對於一個長度為 $n$ 的字串 $S$ 和一個長度為 $n$ 的 01 字串 $e$，會產生一個加密過後的字串 $T$，其中加密流程為以下兩個步驟：

1. 如果字串 $e$ 中 $1$ 的出現次數是偶數，則直接進第二步驟，出現次數是奇數則將字串 $S$ 平分成兩等份，兩份順序交換後再接起來，如果字串長度是奇數，則最中間的字元不動位置。
2. 讓 $i$ 從 $1$ 到 $n$ 迭代，如果 $e[i] = 0$ 就將 $S$ 的第一個字元切掉並接到字串 $T$ 的最後一個字元，如果 $e[i] = 1$ 就將 $S$ 的最後一個字元切掉並接到字串 $T$ 的最後一個字元。

以範例一為例，陣列為 10110，其中 1 出現的次數為奇數，因此需要交換字串 $S$ 從 BCAAD 變為 ADABC。接下來執行第二階段，其中過程如下。

<center>

| <center>i</center> | <center>1</center> | <center>2</center> | <center>3</center> | <center>4</center> | <center>5</center> |
| - | - | - | - | - | - |
| e | 1 | 0 | 1 | 1 | 0 |
| S | ADAB | DAB | DA | D | 空字串 |
| T | C | CA | CAB | CABA | CABAD |

</center>

給由 $m$ 個 01 字串的加密表和按照順序加密原字串後得到加密過後的字串，請嘗試還原出原本的字串。
<br />

### 輸入說明

第一行輸入兩個數字 $m, n ~(1 \leq m, n \leq 100)$，接下來有 $m$ 個長度為 $n$ 的 01 字串，最後輸入一個長度為 $n$ 的加密字串，字串均由大寫字母組成。

子題配分
- 60%：$m = 1$
- 40%：無額外限制

<br />

### 輸出說明

輸出解碼後的字串。

<br />

### 範例一：輸入

1 5
10110
CABAD

### 範例一：正確輸出

BCAAD

<br />

### 範例二：輸入

3 6
111110
101101
000000
RETYWQ

### 範例二：正確輸出

QWERTY

<br />

## 提示

範例測資一，如題目所述。

範例測資二過程如下：
1. e = 111110，出現的數量為奇數次，因此需要將字串 "QWERTY" 切半翻轉成 "RTYQWE"，經過 01 字串的轉換後會得到 "EWQYTR"。
2. e = 101101， 出現的數量為偶數次，因此不用翻轉字串，經過 01 字串的轉換後會得到 "RETYWQ"。
3. e = 000000， 出現的數量為偶數自，因此不用翻轉字串，經過 01 字串的轉換後會得到 "RETYWQ"。
<br /><br />

## Python 程式碼

### 加密

依照題目的敘述，試著先寫出加密的程式碼，如果能夠從範例的輸出資料推出輸入資料，接下來再把程式碼運作的過程反過來，就能寫出解碼用的程式碼。

m, n = map(int, input().split())  # 讀取m, n
ops = []  # 儲存操作過程的串列
for i in range(m): ops.append(input())  # 讀取操作過程
s = input()  # 加密前的字串
t = ""  # 加密後的字串

for i in range(m):  # 依序讀取操作過程
    num = 0  # 操作過程中 1 的數量
    op = ops[i]  # 第i個操作過程
    for j in range(n):  # 依序讀取 op 的內容，計算 1 的數量
        if op[j] == '1': num += 1
    if num%2 == 1:  # 如果 1 的數量是奇數，將 s 分成兩半、前後交換
        if n%2 == 0:
            s = s[n//2 :] + s[:n//2]
        else:
            s = s[n//2 + 1 :] + s[n//2] + s[:n//2]
    for j in range(n):  # 依序讀取 op 的內容
        if op[j] == '0':  # 如果是 0，取下 s 最前面的字母加到 t 的最後面
            t = t + s[0]
            s = s[1:]
        elif op[j] == '1':  # 如果是 1，取下 s 最後面的字母加到 t 的最後面
            t = t + s[-1]
            s = s[:-1]
    if i < m-1:  # 如果還有未讀取的操作過程，重設 s 和 t 的內容
        s = t
        t = ""

print(t)  # 印出加密後的字串

<br /><br />

### 解碼

於 ZeroJudge 測試結果，最長運算時間約為 30 ms，使用記憶體最多約為 3.4 MB，通過測試。

m, n = map(int, input().split())  # 讀取m, n
ops = []  # 儲存操作過程的串列
for i in range(m): ops.append(input())  # 讀取操作過程
s = ""  # 加密前的字串，最後要輸出的答案
t = input()  # 加密後的字串

for i in range(m):  # 倒序讀取操作過程
    num = 0  # 操作過程中 1 的數量
    op = ops[m-i-1]  # 第 m-i-1 個操作過程
    for j in range(n):  # 倒序讀取 op 的內容，計算 op 中 1 的數量，同時將 t 還原為 s
        if op[n-j-1] == '0':  # 如果是 0，取下 t 最後面的字母加到 s 的最前面
            s = t[-1] + s  
            t = t[:-1]
        elif op[n-j-1] == '1':  # 如果是 1，取下 t 最後面的字母加到 s 的最後面
            num += 1
            s = s + t[-1]
            t = t[:-1]
    if num%2 == 1:  # 如果 1 的數量是奇數，將 s 分成兩半、前後交換
        if n%2 == 0:
            s = s[n//2 :] + s[:n//2]
        else:
            s = s[n//2 + 1 :] + s[n//2] + s[:n//2]
    if i < m-1:  # 如果還有未讀取的操作過程，重設 s 和 t 的內容
        t = s
        s = ""

print(s)  # 印出解碼後的字串

<br /><br />

## C++ 程式碼

### 加密

#include <iostream>
#include <string>
using namespace std;

int main() {
    int m, n; cin >> m >> n;  // 讀取m, n
    string ops[m];  // 儲存操作過程的串列
    for(int i=0; i<m; i++) cin >> ops[i];  // 讀取操作過程
    string s; cin >> s;  // 加密前的字串
    string t = "";  // 加密後的字串

    for(int i=0; i<m; i++) {  // 依序讀取操作過程
        int num = 0;  // 操作過程中 1 的數量
        string op = ops[i];  // 第i個操作過程
        for(auto c : op) {  // 依序讀取 op 的內容，計算 1 的數量
            if (c == '1') num++;
        }
        if (num%2 == 1) {  // 如果 1 的數量是奇數，將 s 分成兩半、前後交換
            if (n%2 == 0) s = s.substr(n/2, n/2) + s.substr(0, n/2);
            else s = s.substr(n/2 + 1, n/2) + s[n/2] + s.substr(0, n/2);
        }
        for(auto c : op) {  // 依序讀取 op 的內容
            if (c == '0') {  // 如果是 0，取下 s 最前面的字母加到 t 的最後面
                t = t + s[0];
                s = s.substr(1, s.size()-1);
            } else if (c == '1') {  // 如果是 1，取下 s 最後面的字母加到 t 的最後面
                t = t + s[s.size()-1];
                s = s.substr(0, s.size()-1);
            }
        }
        if (i < m-1) {  // 如果還有未讀取的操作過程，重設 s 和 t 的內容
            s = t;
            t = "";
        }
    }
    cout << t << endl;  // 印出加密後的字串
    return 0;
}

<br /><br />

### 解碼

於 ZeroJudge 測試結果，最長運算時間約為 5 ms，使用記憶體最多約為 368 kB，通過測試。

#include <iostream>
#include <string>
using namespace std;

int main() {
    int m, n; cin >> m >> n;  // 讀取m, n
    string ops[m];  // 儲存操作過程的串列
    for(int i=0; i<m; i++) cin >> ops[i];  // 讀取操作過程
    string s = "";  // 加密前的字串
    string t; cin >> t; // 加密後的字串

    for(int i=0; i<m; i++) {  // 依序讀取操作過程
        int num = 0;  // 操作過程中 1 的數量
        string op = ops[m-i-1];  // 第 m-i-1 個操作過程
        for(int j=0; j<n; j++) {  // 倒序讀取 op 的內容，計算 op 中 1 的數量，同時將 t 還原為 s
            if (op[n-j-1] == '0') {  // 如果是 0，取下 t 最後面的字母加到 s 的最前面
                s = t[t.size()-1] + s;
                t = t.substr(0, t.size()-1);
            } else if (op[n-j-1] == '1') {  // 如果是 1，取下 t 最後面的字母加到 s 的最後面
                num++;
                s = s + t[t.size()-1];
                t = t.substr(0, t.size()-1);
            }
        }
        if (num%2 == 1) {  // 如果 1 的數量是奇數，將 s 分成兩半、前後交換
            if (n%2 == 0) s = s.substr(n/2, n/2) + s.substr(0, n/2);
            else s = s.substr(n/2 + 1, n/2) + s[n/2] + s.substr(0, n/2);
        }
        if (i < m-1) {  // 如果還有未讀取的操作過程，重設 s 和 t 的內容
            t = s;
            s = "";
        }
    }
    cout << s << endl;  // 印出解碼後的字串
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`