i400: 2. 字串解碼
Tags : APCS 字串 模擬
Accepted rate : 263人/285人 ( 92% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-06-13 00:33

Content

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


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

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

 

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

Input

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

 

子題配分

  • (60%): $m = 1$
  • (40%): 無額外限制
Output

輸出解密後的字串。

Sample Input #1
1 5
10110
CABAD
Sample Output #1
BCAAD
Sample Input #2
3 6
111110
101101
000000
RETYWQ
Sample Output #2
QWERTY
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1K
公開 測資點#9 (5%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1K
公開 測資點#11 (5%): 1.0s , <1K
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
Hint :

範例測資一,如題目所述

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

Tags:
APCS 字串 模擬
出處:
2022年6月APCS [管理者: algo.seacow@...(演算法海牛) ]


ID User Problem Subject Hit Post Date
30855 forkidlai(forkidlai) i400
109 2022-06-16 17:09
30842 20060705sean(pneumonoultrami...) i400
此題之梗
215 2022-06-15 20:13
30840 doo74123(unknown) i400
python ya stillTLE
87 2022-06-15 19:21
30803 mumulin(Mumu Lin) i400
解題想法
269 2022-06-13 14:43
30799 810339@fhsh....(冠傑(真 •鳳薪水題王)) i400
思路(暴力解)
374 2022-06-13 03:34