prithivMLmods/Coder-Stat

1<h1>毒蛇の脱走(Snake Escaping)</h1>2 3<p>4  JOI 研究所では<var>2^L</var> 匹の毒蛇を飼っており，それぞれ<var>0, 1, ..., 2^L - 1</var> の番号が付けられている．すべての毒蛇は頭から順に<var>L</var> 個の部分に分かれており，それぞれの部分は青または赤である．毒蛇<var>i</var> に対し，<var>i</var> を2進表記して<var>i =</var> $\sum_{k=1}^{L}$<var> c_k2^{L-k} (0 \leq c_k \leq 1)</var> とおいたとき，5</p>6<ul>7<li> <var>c_k = 0</var> であれば，毒蛇<var>i</var> の頭から数えて<var>k</var> 番目の部分は青であり，</li>8<li> <var>c_k = 1</var> であれば，毒蛇<var>i</var> の頭から数えて<var>k</var> 番目の部分は赤である．</li>9</ul>10<p>11各毒蛇には毒性と呼ばれる0 以上9 以下の整数値が定まっている．<span>0</span>, <span>1</span>, <span>2</span>, <span>3</span>, <span>4</span>, <span>5</span>, <span>6</span>, <span>7</span>, <span>8</span>, <span>9</span> からなる長さ<var>2^L</var> の文字列<var>S</var> が与えられ，その<var>i</var> 文字目(<var>1 \leq i \leq 2^L</var>) は毒蛇<var>i - 1</var> の毒性を表す．12</p>13 14<p>15  毒蛇たちの動きは素早いので，JOI 研究所からは，よく毒蛇たちが脱走してしまう．JOI 研究所には脱走した毒蛇を目撃した周辺住民から苦情が寄せられる．16</p>17 18<p>19  あなたには，<var>Q</var> 日間にわたる苦情の情報が与えられる．<var>d</var> 日目(<var>1 \leq d \leq Q</var>) に寄せられた苦情は， <span>0</span>, <span>1</span>, <span>?</span>からなる長さ<var>L</var> の文字列<var>T_d</var> として表され，20</p>21 22<ul>23<li> <var>T_d</var> の<var>j</var> 文字目(<var>1 \leq j \leq L</var>) が<span>0</span> の場合は，<var>d</var> 日目に脱走したすべての毒蛇の頭から数えて<var>j</var> 番目の部分が青であることを表し，</li>24<li> <var>T_d</var> の<var>j</var> 文字目(<var>1 \leq j \leq L</var>) が<span>1</span> の場合は，<var>d</var> 日目に脱走したすべての毒蛇の頭から数えて<var>j</var> 番目の部分が赤であることを表し，</li>25<li> <var>T_d</var> の<var>j</var> 文字目(<var>1 \leq j \leq L</var>) が<span>?</span> の場合は，<var>d</var> 日目に脱走した毒蛇の頭から数えて<var>j</var> 番目の部分については，周辺住民からは情報が与えられなかったことを表す．</li>26</ul>27 28<p>29  苦情はすべて正確な情報である．脱走した毒蛇はJOI 研究所の職員がその日のうちに捕獲する．捕獲された毒蛇が，翌日以降に再び脱走することはあり得る．30</p>31 32<p>33  毒蛇の脱走によるリスクを見積もるために，JOI 研究所のK 理事長は脱走した可能性のある毒蛇の毒性の合計を知りたい．あなたの仕事は，<var>Q</var> 日間にわたる苦情の情報から，それぞれの日ごとに，その日に脱走した可能性のある毒蛇の毒性の合計を求めるプログラムを作成することである．34</p>35 36 37<h3>課題</h3>38 39<p>40  毒蛇の毒性を表す文字列<var>S</var> と，<var>Q</var> 日間の苦情の情報が与えられるので，それぞれの日ごとに，その日に脱走した可能性のある毒蛇の毒性の合計を求めるプログラムを作成せよ．41</p>42<p>43  メモリ制限が小さいことに注意すること．44</p>45 46 47<h3>入力</h3>48 49<p>50  標準入力から以下の入力を読み込め．51</p>52 53<ul>54  <li> 1 行目には，整数<var>L, Q</var> が空白を区切りとして書かれている．これらは順に，毒蛇の部分の個数と，苦情の寄せられる日数を表す．55    </li>56  <li> 2 行目には，長さ<var>2^L</var> の文字列<var>S</var> が書かれている．この文字列は毒蛇の毒性を表す．</li>57  <li> 続く<var>Q</var> 行のうちの<var>d</var> 行目(<var>1 \leq d \leq Q</var>) には，長さ<var>L</var> の文字列<var>T_d</var> が書かれている．この文字列は<var>d</var> 日目の苦情を表す．</li>58  </ul>59    60<h3>出力</h3>61<p>62  標準出力に<var>Q</var> 行で出力せよ．<var>d</var> 行目には，<var>d</var> 日目に脱走した可能性のある毒蛇の毒性の合計を表す整数を出力せよ．63</p>64 65 66<h3>制限</h3>67<p>68  すべての入力データは以下の条件を満たす．69</p>70<ul>71<li><var> 1 \leq L \leq 20</var>．</li>72<li><var> 1 \leq Q \leq 1 000 000</var>．</li>73<li><var>S</var> は長さ<var>2^L</var> の文字列である．</li>74<li> 文字列<var>S</var> は<span>0</span>, <span>1</span>, <span>2</span>, <span>3</span>, <span>4</span>, <span>5</span>, <span>6</span>, <span>7</span>, <span>8</span>, <span>9</span> からなる．</li>75<li> <var>T_d</var> は長さ<var>L</var> の文字列である(<var>1 \leq d \leq Q</var>)．</li>76<li> 文字列<var>T_d</var> は<span>0</span>, <span>1</span>, <span>?</span> からなる(<var>1 \leq d \leq Q</var>)．</li>77</ul>78 79<!--80小課題81小課題1 [5 点]82以下の条件を満たす．83 L ≦ 10．84 Q ≦ 1 000．85小課題2 [7 点]86 L ≦ 10 を満たす．87小課題3 [10 点]88 L ≦ 13 を満たす．89小課題4 [53 点]90 Q ≦ 50 000 を満たす．91小課題5 [25 点]92 追加の制限はない．93  -->94 95 96<h3>入出力例</h3>97<h3>入力例1 </h3>98<pre>993 5100123456781010001020??1031?0104?11105???106</pre>107<h3>出力例1</h3>108<pre>109111010111121121211336114</pre>115 116<p>117  この入力例では，<var>L = 3</var> である．3 つの部分に分かれた毒蛇が，全部で<var>2^3 = 8</var> 匹いる．苦情は5 日間にわたって寄せられる．118</p>119 120<ul>121<li> 1 日目に脱走した可能性のある毒蛇は，毒蛇0 のみである．毒性の合計は1 である．</li>122<li> 2 日目に脱走した可能性のある毒蛇は，毒蛇0, 1, 2, 3 である．毒性の合計は10 である．</li>123<li> 3 日目に脱走した可能性のある毒蛇は，毒蛇4, 6 である．毒性の合計は12 である．</li>124<li> 4 日目に脱走した可能性のある毒蛇は，毒蛇3, 7 である．毒性の合計は12 である．</li>125<li> 5 日目に脱走した可能性のある毒蛇は，毒蛇0, 1, 2, 3, 4, 5, 6, 7 である．毒性の合計は36 である．</li>126</ul>127 128 129<h3>入力例2</h3>130<pre>1314 813231415926535897931330101134?01?135??1?136?0??1371?0013801?1139??10140????141</pre>142<h3>出力例2</h3>143<pre>144914518146381473014814149151502015180152</pre>153 154 155<br/>156<p>157  <a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/"><img alt="クリエイティブ・コモンズ・ライセンス" style="border-width:0" src="https://i.creativecommons.org/l/by-sa/4.0/80x15.png"/></a>158  <br/>159  160  <a href="https://www.ioi-jp.org/joi/2017/2018-ho/index.html">情報オリンピック日本委員会作 『第17 回日本情報オリンピック(JOI 2017/2018) 本選』</a>161</p>162 163