prithivMLmods/Coder-Stat

1 2 3 4<h1>JOI国のお散歩事情 (Walking in JOI Kingdom)</h1>5 6<h2>  問題</h2>7<p>8JOI 国には東西に走る 1 本の十分に長い道路がある．JOI 国の王宮が道路沿いにあり，JOI 国における道路沿いの位置は整数 A で表される．A = 0 のときは王宮の位置を表す．A > 0 のときは，王宮から東へ A メートル進んだ位置を表す．A < 0 のときは，王宮から西へ -A メートル進んだ位置を表す．9</p>10 11<p>12JOI 国の道路沿いには N 軒の家があり，家には西から順に 1 から N までの番号が付けられている．JOI 国には N 人の国民がいて，国民には 1 から N までの番号が付けられている．家 i には国民 i が住んでいる．家 i の位置は 0 でない偶数 A<sub>i</sub> で表される．A<sub>1</sub>, ..., A<sub>N</sub> は全て異なる．13</p>14 15<p>16JOI 国では，近年国民の運動不足が問題になっている．国民の健康が気になった JOI 国の王様は，国民全員に散歩をする命令を出した．王様が命令を出すと，全ての国民は一斉に東向きまたは西向きに歩き始める．それぞれの国民がどちらの向きに歩き始めるかは，国民ごとに決まっている．全ての国民は，歩くときは 1 秒あたり 1 メートルの速度で歩く．17</p>18 19<p>20JOI 国の国民は皆おしゃべりが大好きである．散歩の途中にほかの国民に出会うと，その場所で立ち止まって世間話を始めてしまう．すでに立ち止まっている国民に出会った場合も同様である．一度立ち止まった国民は，再び歩き出すことはない．21</p>22 23<p>24JOI 国には Q 人の重要人物がいる．JOI 国の王様は，命令が出されてから T 秒後の，Q 人の重要人物の位置を把握しておきたい．命令が出されてから T 秒後の，Q 人の重要人物の位置を求めるプログラムを作成せよ．25</p>26 27 28<h2>  入力</h2>29<p>30入力は，1 + N + Q 行からなる．31</p>32 33<p>341 行目には，3 つの整数 N，T，Q (1 ≦ N ≦ 100000 (= 10<sup>5</sup>), 0 ≦ T ≦ 10<sup>18</sup>, 1 ≦ Q ≦ 1000，1 ≦ Q ≦ N) が空白を区切りとして書かれている．これは，JOI 国に家が N 軒あり，王様が命令を出してから T 秒後の，Q 人の重要人物の位置を把握しておきたいことを表す．35</p>36 37<p>38続く N 行のうち i 行目には，2 つの整数 A<sub>i</sub>, D<sub>i</sub> (-10<sup>18</sup> ≦ A<sub>i</sub> ≦ 10<sup>18</sup>, A<sub>i</sub> は 0 でない偶数, 1 ≦ D<sub>i</sub> ≦ 2) が空白を区切りとして書かれている．A<sub>i</sub> は家 i の位置を表す偶数である．すべての i (1 ≦ i ≦ N - 1) について，A<sub>i</sub> < A<sub>i+1</sub> を満たす．D<sub>i</sub> は命令が出された後に国民 i が歩き始める方向を表す．D<sub>i</sub> = 1 のときは国民 i は東向きに歩き始める．D<sub>i</sub> = 2 のときは国民 i は西向きに歩き始める．39</p>40 41<p>42続く Q 行のうち i 行目には，整数 X<sub>i</sub> (1 ≦ X<sub>i</sub> ≦ N) が書かれている．これは，i 番目の重要人物が家 X<sub>i</sub> に住んでいることを表す．すべての i (1 ≦ i ≦ Q - 1) について，X<sub>i</sub> < X<sub>i+1</sub> を満たす．43</p>44 45<p>46与えられる 5 つの入力データのうち，入力 1 では N ≦ 100，T ≦ 10000を満たす．また，入力 2 では N ≦ 5000 を満たす．また，入力 3 では，ある整数 M (1 ≦ M ≦ N - 1) があって，すべての i (1 ≦ i ≦ M) について D<sub>i</sub> = 1，すべての j (M + 1 ≦ j ≦ N) について D<sub>j</sub> = 2 を満たす．また，入力 1，2，3 では，入力に与えられる整数の絶対値は 1000000000 (= 10<sup>9</sup>) を超えない．入力 4，5 では，与えられる整数が 32 ビット符号付き整数の範囲に収まらないことに注意せよ．47</p>48 49<h2>  出力</h2>50<p>51出力は Q 行からなる．52</p>53 54<p>55i 行目 (1 ≦ i ≦ Q) には，王様が命令を出してから T 秒後の，i 番目の重要人物の位置を表す整数を出力せよ．この値が整数であることは，問題文の条件より保証されている．56</p>57 58<h2>  入出力例</h2>59 60<h3>入力例 1</h3>61 62 63  <pre>645 5 365-8 166-4 267-2 2684 26910 170171372573</pre>74 75   <h3>出力例 1</h3>76 77   <pre>78-679-6801581</pre>82 83<h3>入力例 2</h3>84  <pre>857 18 586-100 187-56 288-34 189-30 190-22 191-4 29218 293194395496597798</pre>99 100 101   <h3>出力例 2</h3>102 103  <pre>104-82105-16106-13107-131080109</pre>110 111 112<div class="source">113<p class="source">114<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>115</p>116<p class="source">117 118<a href="https://www.ioi-jp.org/joi/2015/2016-yo/index.html">情報オリンピック日本委員会作 『第 15 回日本情報オリンピック JOI 2015/2016 予選競技課題』</a>119 120</p>121</div>122