prithivMLmods/Coder-Stat

1 2<h1><font color="#000">Problem E:</font> <u>The Genome Database of All Space Life</u></h1>3<!-- end en only -->4 5 6<p>7In 2300, the Life Science Division of Federal Republic of Space starts8a very ambitious project to complete the genome sequencing of all9living creatures in the entire universe and develop the genomic10database of all space life.11Thanks to scientific research over many years, it has been known that12the genome of any species consists of at most 26 kinds of13molecules, denoted by English capital letters (<i>i.e.</i> <tt>A</tt>14to <tt>Z</tt>).15</p>16<!-- end en only -->17 18<!-- begin en only -->19<p>20What will be stored into the database are plain strings consisting of21English capital letters.22In general, however, the genome sequences of space life include23frequent repetitions and can be awfully long.24So, for efficient utilization of storage, we compress <i>N</i>-times25repetitions of a letter sequence <i>seq</i> into26<i>N</i><tt>(</tt><i>seq</i><tt>)</tt>, where <i>N</i> is a natural 27number greater than or equal to two and the length of <i>seq</i> is at28least one.29When <i>seq</i> consists of just one letter <i>c</i>, we may omit parentheses and write <i>Nc</i>.30</p>31<!-- end en only -->32 33<!-- begin en only -->34<p>35For example, a fragment of a genome sequence:36</p><blockquote>37<tt>ABABABABXYXYXYABABABABXYXYXYCCCCCCCCCC</tt>38</blockquote>39<p>can be compressed into:</p>40<blockquote>41<tt>4(AB)XYXYXYABABABABXYXYXYCCCCCCCCCC</tt>42</blockquote>43<p>by replacing the first occurrence of <tt>ABABABAB</tt> with its compressed form.44Similarly, by replacing the following repetitions of <tt>XY</tt>,45<tt>AB</tt>, and <tt>C</tt>, we get:</p>46<blockquote>47<tt>4(AB)3(XY)4(AB)3(XY)10C</tt>48</blockquote>49<p>Since <tt>C</tt> is a single letter, parentheses are omitted in this50compressed representation.51Finally, we have:</p>52<blockquote>53<tt>2(4(AB)3(XY))10C</tt>54</blockquote>55<p>by compressing the repetitions of <tt>4(AB)3(XY)</tt>.56As you may notice from this example, parentheses can be nested.57<p></p>58<!-- end en only -->59 60<!-- begin en only -->61<p>62Your mission is to write a program that uncompress compressed genome63sequences.64</p>65<!-- end en only -->66 67 68<h2>Input</h2>69 70 71<!-- begin en only -->72<p>The input consists of multiple lines, each of which contains a73character string <i>s</i> and an integer <i>i</i> separated by a74single space. 75</p>76<!-- end en only -->77 78 79<!-- begin en only -->80<p>81The character string <i>s</i>, in the aforementioned manner,82represents a genome sequence.83You may assume that the length of <i>s</i> is between 1 and 100,84inclusive.85However, of course, the genome sequence represented by <i>s</i> may be86much, much, and much longer than 100.87You may also assume that each natural number in <i>s</i> representing the88number of repetitions is at most 1,000. 89</p>90<!-- end en only -->91 92<!-- begin en only -->93<p>94The integer <i>i</i> is at least zero and at most one million. 95</p>96<!-- end en only -->97 98 99<!-- begin en only -->100<p>101A line containing two zeros separated by a space follows the last input line and indicates102the end of the input.103</p>104<!-- end en only -->105 106 107<h2>Output</h2>108 109<!-- begin en only -->110<p>111For each input line, your program should print a line containing the112<i>i</i>-th letter in the genome sequence that <i>s</i> represents.113If the genome sequence is too short to have the <i>i</i>-th element,114it should just print a zero.115No other characters should be printed in the output lines.116 117Note that in this problem the index number begins from zero rather118than one and therefore the initial letter of a sequence is its zeroth element.119</p>120<!-- end en only -->121 122 123<h2>Sample Input</h2>124 125<pre>126ABC 3127ABC 01282(4(AB)3(XY))10C 301291000(1000(1000(1000(1000(1000(NM)))))) 9999991300 0131</pre>132 133 134<h2>Output for the Sample Input</h2>135 136<pre>1370138A139C140M141</pre>142 143