850 . 貓咪國的機密

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

BINS

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

apcsc apcsc-exam5

Description

方塊國與貓咪國的戰事正進行著。經過一番研究，方塊國抓到貓咪國情治單位都顧著吸草和睡覺，根本沒有好好加密軍事機密！方塊國完美破譯了貓咪國的訊息，發現貓咪國經過編碼的訊息只包含數字、括號、大寫字母三種字元，規則如下：

  1. 單一字母是合法的密文，代表那個字母。例如，C 解碼後會得到 C
  2. 對於一段長度至少是 1 的合法密文 $S$ 和一個介於 1 到 999 的十進位數字 $K$，$K\texttt{(}S\texttt{)}$ 代表將 $S$ 解密後重複 $K$ 次。例如，5(X) 解碼後會得到 XXXXX
  3. 對於兩段合法的密文 $S, T$，$ST$ 代表將兩段密文分別解密後接在一起。例如，A3(H) 解碼後會得到 AHHH。

這天，方塊國又攔截到一段貓咪國發出的訊息 $t$，並得知其中一些位置帶有關鍵訊息。方塊國決定將 $t$ 解碼，還原出原本的訊息 $s$，而關鍵訊息就藏在 $s$ 的前幾個字母中。請你幫助方塊國，找出這段訊息解碼後的實際長度，並找出所有關鍵訊息。

Input Format

第一行是字串 $t$，由大寫英文字母、數字、括號組成，代表訊息 $s$ 經過貓咪國編碼後的結果。

接下來的一行有一個整數 $Q$，代表關鍵訊息的字元數量。

接下來的一行有 $Q$ 個以空白分隔的整數，第 $i$ 個數 $x_i$ 代表關鍵訊息的第 $i$ 個字元是 $s_{x_i}$，保證 $s_{x_i}$ 存在。

  • $1 \le |t| \le 10^ 6$
  • 存在一個 $s$ 使得 $t$ 是 $s$ 編碼後的結果。換句話說，$t$ 必定是合法的密文
  • $1 \le Q \le 10$
  • $1 \le x_i \le 10^ {15}$
  • 連續的數字不超過三個字元
  • 任一組括號中間必定有至少一個字元

Output Format

若 $|s| \le 10^ {15}$，請在第一行輸出一個整數 $l$ 代表 $|s| = l$。否則輸出一行 Too loooong!。

第二行請輸出 $Q$ 個大寫字母，依序代表每個詢問的答案。

Sample Input 1

2(3(OAO)2(MEOW))W10(A)
5
1 45 2 15 8

Sample Output 1

45
OAAEA

Sample Input 2

1(1(1(1(1(1(1(A)))))))
1
1

Sample Output 2

1
A

Sample Input 3

999(999(999(999(999(999(ABC))))))
10
1 2 3 4 5 6 7 8 9 10

Sample Output 3

Too loooong!
ABCABCABCA

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 3~8, 34~36 $|s| \le 10^ 5$ 10
3 9~21, 34~36 $|t| \le 1000$ 30
4 0~36 無額外限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 4
1 1000 524288 65536 1 4
2 1000 524288 65536 1 4
3 1000 524288 65536 2 4
4 1000 524288 65536 2 4
5 1000 524288 65536 2 4
6 1000 524288 65536 2 4
7 1000 524288 65536 2 4
8 1000 524288 65536 2 4
9 1000 524288 65536 3 4
10 1000 524288 65536 3 4
11 1000 524288 65536 3 4
12 1000 524288 65536 3 4
13 1000 524288 65536 3 4
14 1000 524288 65536 3 4
15 1000 524288 65536 3 4
16 1000 524288 65536 3 4
17 1000 524288 65536 3 4
18 1000 524288 65536 3 4
19 1000 524288 65536 3 4
20 1000 524288 65536 3 4
21 1000 524288 65536 3 4
22 1000 524288 65536 4
23 1000 524288 65536 4
24 1000 524288 65536 4
25 1000 524288 65536 4
26 1000 524288 65536 4
27 1000 524288 65536 4
28 1000 524288 65536 4
29 1000 524288 65536 4
30 1000 524288 65536 4
31 1000 524288 65536 4
32 1000 524288 65536 4
33 1000 524288 65536 4
34 1000 524288 65536 2 3 4
35 1000 524288 65536 2 3 4
36 1000 524288 65536 2 3 4
Submit
Back to Top