prithivMLmods/Coder-Stat

1 2 3<script type="text/x-mathjax-config">4  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});5</script>6<script language="JavaScript" type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML">7</script>8 9 10<H1> バームクーヘン(Baumkuchen)11</H1>12<br/>13 14<p>15JOI 君は妹のJOI 子ちゃんとJOI 美ちゃんと一緒におやつを食べようとしている．今日のおやつは3 人の大好物のバームクーヘンだ．16</p>17 18<p>19バームクーヘンは下図のような円筒形のお菓子である．3 人に分けるために，JOI 君は半径方向に刃を3回入れて，これを3 つのピースに切り分けなければならない．ただしこのバームクーヘンは本物の木材のように固いので，刃を入れるのは簡単ではない．そのためこのバームクーヘンにはあらかじめ $N$ 個の切れ込みが入っており，JOI 君は切れ込みのある位置でのみ切ることができる．切れ込みに1 から $N$ まで時計回りに番号をふったとき，$1 \leq i \leq N - 1$ に対し， $i$ 番目の切れ込みと$i + 1$ 番目の切れ込みの間の部分の大きさは $A_i$ である．また $N$ 番目の切れ込みと1 番目の切れ込みの間の部分の大きさは $A_N$ である．20</p>21 22<br>23<center>24<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_baumkuchen_1"><br>25図1: バームクーヘンの例 $N = 6, A_1 = 1, A_2 = 5, A_3 = 4, A_4 = 5, A_5 = 2, A_6 = 4$26</center><br><br>27 28 29 30 31<h2>課題</h2>32 33<p>34切れ込みの個数 $N$ と，各部分の大きさを表す整数 $A_1,...,A_N$ が与えられる．バームクーヘンを3 つに切り分けたときの，最も小さいピースの大きさの最大値を出力するプログラムを作成せよ．35</p>36 37 38<h2>入力</h2>39<p>40標準入力から以下のデータを読み込め．41</p>42<ul>43<li> 1 行目には，整数 $N$ が書かれている．これはバームクーヘンに $N$ 個の切れ込みがあることを表す．</li>44<li> 続く$N$ 行のうちの $i$ 行目$(1 \leq i \leq N)$ には，整数 $A_i$ が書かれている．これは $i$ 番目の切れ込みと $i + 1$ 番目の切れ込みの間の部分 ($i = N$ のときは $N$ 番目の切れ込みと1 番目の切れ込みの間の部分) の大きさが $A_i$ であることを表す．</li>45</ul>46 47<h2>出力</h2>48<p>49標準出力に，バームクーヘンを3 つに切り分けたときの，最も小さいピースの大きさの最大値を表す整数を1 行で出力せよ．50</p>51 52 53<h2>制限</h2>54<p>55すべての入力データは以下の条件を満たす．56</p>57 58<ul>59<li>$3 \leq N \leq 100000$</li>60<li>$1 \leq A_i \leq 1000000000 (1 \leq i \leq N)$</li>61</ul>62 63<h2>入出力例</h2>64 65  <h3>入力例 1 </h3>  66 67  <pre>68669170571472573274475</pre>76 77  <h3>出力例 1 </h3>  78 79  <pre>80681</pre>82 83<br>84 85<center>86<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_baumkuchen_2"><br>87図2: 1 番目の切れ込みと3 番目の切れ込みと5 番目の切れ込みで切るのが最善である．88</center><br><br>89 90 91  <h3>入力例 2 </h3>  92 93  <pre>94309519634974498139930100110191023103710471052010612107210844109611091114411231113171142011533116181174811823119191203112124122501234312415125</pre>126 127  <h3>出力例 2 </h3>  128 129  <pre>130213131</pre>132<br>133 134 135<div class="source">136<p class="source">137問題文と自動審判に使われるデータは、<a href="http://www.ioi-jp.org">情報オリンピック日本委員会</a>が作成し公開している問題文と採点用テストデータです。138</p>139</div>140