prithivMLmods/Coder-Stat

1 2 3 4<H1>つらら</H1>5 6<h2> 問題</h2>7<p>8カナダに住む JOI 君の家の軒下には,立派なつららが出来ている.せっかくなので,JOI 君はつららについて調べてみることにした.9</p>10<p>11JOI 君の家の軒下には N 本(2 &le; N &le; 100000 = 10<sup>5</sup> )のつららが出来ている.これらのつららは一直線上に並んでおり,軒下の左端から i cm(1 &le; i &le; N )の位置に i 本目のつららが出来ている.i 本目のつららの長さは最初 ai cm(ai は 1 以上の整数)である.これらのつららは,次のような規則によって伸びていく:12</p>13 14<ul>15<li> i 本目のつららは,i − 1 本目のつららと i + 1 本目のつららの両方よりも長い場合にのみ,1 時間につき 1 cm ずつ伸びる(ただし,両端のつららに関しては片方の隣のみ考える.すなわち,1 本目のつららは 2 本目のつららより長ければ伸び,N 本目のつららは N − 1 本目のつららより長ければ伸びる).16</li>17<li> どのつららも,L cm(2 &le; L &le; 50000)に達した瞬間に,根元から折れる(折れたつららは,以後長さ 0 cm のつららとみなす)18.19</li>20</ul>21<p>22最初の段階で,隣り合う 2 本のつららの長さはすべて異なっている.このとき,十分な時間が経過すれば,N 本すべてのつららが折れて長さ 0 cm となる.JOI 君は,つららがこのような状態になるまでの時間を知りたくなった.23</p>24 25<p>26N 本のつららの最初の長さとつららの限界の長さ L が与えられると,すべてのつららが折れるまでにかかる時間を求めるプログラムを作成せよ.27</p>28 29 30<h2>入力</h2>31<!--32<p>33入力ファイルのファイル名は input.txt である.34</p>35-->36 37<p>38入力の 1 行目には,つららの本数を表す整数 N とつららの限界の長さを表す整数39L が,空白を区切りとしてこの順に書かれている.入力の i + 1 行目 (1 &le; i &le; N) に40は, i 本目のつららの最初の長さを表す整数 ai (1 &le; ai &lt; L) が書かれている.41</p>42 43<p>44採点用データのうち,配点の 30% 分については,N &le;45500 かつ L &le; 461000 を満47たす.48</p>49 50<h2> 出力</h2>51<!--52<p>53出力ファイルのファイル名は output.txt である.54</p>55-->56 57<p>58<!--output.txt-->出力 は,すべてのつららが折れるまでにかかる時間を表す 1 つの整数のみを含む 1 行からなる.59</p>60 61<h2> 入出力例</h2>62 63<h3>入力例 1</h3>  64 65<pre>664 667468269370571</pre>72 73<h3>出力例 1</h3>74 75<pre>76877</pre>78 79<p>80例 1 の場合,1, 2, 3, 4 本目のつららは,それぞれ 2, 8, 4, 1 時間後に折れる.した81がって,すべてのつららが折れるまでにかかる時間は 8 時間であるので,8 を出力82する.83</p>84 85 86<br>87 88<h3>入力例 2</h3>  89 90<pre>916 1092393494195996597198</pre>99 100<h3>出力例 2</h3>101 102<pre>10315104</pre>105 106 107<div class="source">108<p class="source">109上記問題文と自動審判に使われるデータは、<a href="http://www.ioi-jp.org">情報オリンピック日本委員会</a>が作成し公開している問題文と採点用テストデータです。110</p>111</div>112 113 114 115