字串解碼 (APCS 2022-06 中級)

小虎對資訊隱藏很有興趣，他設計了一個編碼方式將一個字串中的字元順序調換，產生一個和原字串不相同的字串，藉以隱藏原本的資訊。首先，小虎定義了一個轉換操作 \(t = f(s, e)\)，即根據 \(s\) 與 \(e\) 計算出另一個字串 \(t\)，其中 \(s\) 是一個由大寫英文字母組成的字串，\(e\) 是一個 \(0/1\) 字串（由 \(0\) 與 \(1\) 組成），兩者長度均為 \(n\)。轉換方式有兩大步驟：

1. 若 \(e\) 中的 \(1\) 的個數為奇數，則將 \(s\) 平分成兩半，然後將前半段與後半段交換，若 \(s\) 的長度為奇數，則正中間的字元不變。若 \(e\) 中的 \(1\) 的個數為偶數，則 \(s\) 不改變。
2. 從 \(i = 0\) 到 \(n - 1\)，依序根據 \(e\) 的第 \(i\) 個字元 \(e[i]\) 與 \(s\) 來決定 \(t\) 的第 \(i\) 個字元 \(t[i]\)：若 \(e[i] = 0\)，則取出 \(s\) 的第一個字元給 \(t[i]\)，並刪除 \(s\) 的第一個字元；若 \(e[i] = 1\)，則取出 \(s\) 的最後一個字元給 \(t[i]\)，並刪除 \(s\) 的最後一個字元。

以 \(s = \texttt{BCAAD}\) 與 \(e = \texttt{10110}\) 為例，因為 \(e\) 中有 \(3\) 個 \(1\)，所以第一步將 \(s\) 的前半段 \(\texttt{BC}\) 與後半段 \(\texttt{AD}\) 交換，\(s\) 變成 \(\texttt{ADABC}\)。第二步驟共有 \(5\) 次操作，詳細如下表，每次操作參考的字元 \(e[i]\) 以及操作後的 \(s\) 與 \(t\) 記錄於表的第 \(i\) 個直欄。

小虎選定了 \(m\) 個 \(0/1\) 字串（\(e_0, e_1, \ldots, e_{m-1}\)）做為編碼表，針對原始字串 \(s_0\) 的編碼方式為進行上述的轉換 \(m\) 次，第 \(j\) 次轉換的結果為 \(s_j = f(s_{j-1}, e_{j-1})\)，最後得到的 \(s_m\) 就是編碼結果。

請寫一支程式，幫助小虎進行訊息的解碼，意即針對一個轉換後的字串，參考小虎的編碼表，計算出原始字串。

輸入格式

輸入的第一行有 \(2\) 個不超過 \(100\) 的正整數 \(m\) 與 \(n\)，分別為編碼表中 \(0/1\) 字串的個數以及每個 \(0/1\) 字串的長度。接下來 \(m\) 行，依序是 \(e_0, e_1, \ldots, e_{m-1}\)。最後一行是一個長度為 \(n\) 的字串，表示小虎收到的訊息，該字串由英文大寫字母組成。

輸出格式

一個字串，為編碼前的原始字串。

範例輸入 1

1 5
10110
CABAD

範例輸出 1

BCAAD

範例說明 1

此為題目中所述之範例。

範例輸入 2

3 6
111110
101101
000000
RETYWQ

範例輸出 2

QWERTY

範例說明 2

\(e_2 = 000000\) 有 \(0\) 個 \(1\)，可知 \(s_2\) 轉換為 \(s_3\) 的過程中不做前後半對調，且由左而右依序取字母後可得 \(s_3 = \texttt{RETYWQ}\)，故 \(s_2 = \texttt{RETYWQ}\)。\(e_1 = 101101\) 有 \(4\) 個 \(1\)，故 \(s_1\) 轉換為 \(s_2\) 的過程中不需前後半對調，直接進行轉換的第二步驟可得 \(s_2\)，故 \(s_1 = \texttt{EWQYTR}\)。\(e_0 = 111110\) 有 \(5\) 個 \(1\)，故 \(s_0\) 轉換為 \(s_1\) 的過程中需要前後半對調，對調後的結果再由右而左取字母得到 \(s_1\)，故原始字串 \(s_0 = \texttt{QWERTY}\)。

評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制均為 \(1\) 秒，依正確通過測資筆數給分。其中：

• 第 1 子題組 60 分：\(m = 1\)。
• 第 2 子題組 40 分：無額外限制。

題目來源

APCS 程式實作中級題本範例，程式實作 2022 年 6 月。

• APCS 官方中級題本範例
• ZeroJudge i400