a138. A. 壓縮字串

Content

這一天，小明在上網學習程式設計時，無意間發現一種壓縮字串的方法：每一個壓縮字串由兩部分組成，第一部分是英文字串，第二部分是數字代表該英文字串連續幾次。也就是說若壓縮字串為 abc3，則其代表的原始字串便為 abcabcabc。

同時各個壓縮字串可以彼此串接，例如若壓縮字串為 s10sprout1，則其代表的原始字串為 sssssssssssprout。

小明覺得這種壓縮方式很神奇，因此想要寫一個程式來計算一個字串壓縮前長怎樣以及原始長度為何，只不過小明目前遇到瓶頸了，希望你能寫一支程式來達成上述的需求以幫助小明。

Input

輸入的第一行包含一個數字 n 代表壓縮字串的長度。
接下來的輸入為一個由小寫英文字母以及數字組成的長度 n 的字串，代表壓縮後的字串。

1 ≤ n ≤ 10⁶
輸入的字串開頭字元為小寫英文字母，結尾字元為數字
保證字串壓縮前的原始長度 ≤ 10⁹

Output

請輸出輸入字串壓縮前的原始長度，若其原始長度小於等於 10⁶ 則在下一行輸出原始字串。

Sample Input #1

4
abc3

Sample Output #1

9
abcabcabc

Sample Input #2

10
s10sprout1

Sample Output #2

16
sssssssssssprout

Sample Input #3

30
meow99999999meoow999999meooow9

Sample Output #3

405000045

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1M
公開測資點#3 (5%): 1.0s , <1M
公開測資點#4 (5%): 1.0s , <1K
公開測資點#5 (5%): 1.0s , <1K
公開測資點#6 (5%): 1.0s , <1K
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#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 , <1K
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1M

Hint ：

20% 壓縮字串不包含彼此串接的情況且數字部分為個位數
30% 壓縮字串不包含彼此串接的情況
50% 無額外限制

Tags:

出處:

2022 資訊之芽算法班入芽考 [管理者： ktlai (K．我已霸榜．Tlai) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」