D - 天下一展開
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
あなたは友人のタクヤ君から独自の方式で圧縮された文字列とそれを展開した後に参照すべき部分の位置と長さを受け取ったので、
参照すべき部分の文字列を得るプログラムを作成する必要がある。
圧縮前の文字列は英字のみからなる文字列である。
そして、英字のみからなる部分文字列 x が n 回繰り返す部分を (x)n に置換することで圧縮を行う。
ただし、|x| \geq 1、n \geq 1 とする。 ( |x| は x の文字列長 )
例えば、 ABABABA は (AB)3A に置換することができる。
また、この置換操作は任意の回数行うことができる。
例えば、AAABBAAABB は (AAABB)2 に置換した後、 さらに、((A)3BB)2 、 ((A)3(B)2)2 と置換することができる。
以上より、圧縮後の文字列 ( input ) は以下のEBNFに従う。
input = string,{string} ;
string = alphabet,{alphabet} | "(",input,")",positive_number ;
alphabet = "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" |
"N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" |
"a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" |
"n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" ;
positive_number = digit_excluding_zero,{digit} ;
digit_excluding_zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
digit = "0" | digit_excluding_zero ;
入力
入力は以下の形式で標準入力から与えられる。
B L N S
- 1 行目には、展開後に参照するべき部分の開始位置 B ( -M \leq B \lt M ) 、参照するべき長さ L ( 1 \leq L \leq 10^5 ) 、 圧縮後の文字列の長さ N ( 1 \leq N \leq 10^4 ) が、スペースで区切られて、それぞれ整数で与えられる。 ただし、M は圧縮前の文字列の長さ とする。
- 2 行目には、圧縮後の文字列 S が与えられる。
- B は、非負の場合は先頭を 0 とした先頭からの位置を表し、負の場合は末尾を -1 とした末尾からの位置を表す。
- B の正負に関係なく、開始位置から末尾方向への L 文字が参照すべき文字列であり、この長さの文字列が得られることは保証される。
- 圧縮前の文字列の長さは 10^{15} を超えない。
部分点
- 圧縮前の文字列の長さをMとし、 L, N \leq 100, M \leq 1000 の入力に正解すると、130 点満点に対して部分点として 50 点が与えられる。
- L, N \leq 100 の入力に正解すると、130 点満点に対して部分点として、さらに 50 点が与えられる。
出力
参照するべき文字列を標準出力に 1 行で出力せよ。
なお、行の終端には改行が必要である。
入力例 1
0 7 6 (AB)3A
出力例 1
ABABABA
入力例 2
-6 5 11 ((A)3(B)2)2
出力例 2
BAAAB