← 返回题目列表

AtCoder · tenka1_2013_qualA_d

D. 天下一展开

中文机器翻译题面 查看原题

問題文

你从你的朋友拓哉那里收到了一个用独特方法压缩的字符串,以及解压后要引用的部分的位置和长度。
需要创建一个程序来获取要引用的部分的字符串。

压缩前的字符串是仅由字母字符组成的字符串。
以及仅由字母字符组成的子字符串 重复 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 。

由上可知,压缩后的字符串( 输入 )如下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 ,您将获得 50 分(总分为 130 分)。 如果您正确回答
  • 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