以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
3 つらら
問題
カナダに住むJOI 君の家の軒下には,立派なつららが出来ている.せっかくなの
で,JOI 君はつららについて調べてみることにした.
JOI 君の家の軒下にはN 本(2 ≦N ≦100000 = 105)のつららが出来ている.こ
れらのつららは一直線上に並んでおり,軒下の左端からi cm(1 ≦i ≦N)の位置
にi 本目のつららが出来ている.i 本目のつららの長さは最初ai cm(ai は1 以上の
整数)である.これらのつららは,次のような規則によって伸びていく:
• i 本目のつららは,i −1 本目のつららとi + 1 本目のつららの両方よりも長い場
合にのみ,1 時間につき1 cm ずつ伸びる(ただし,両端のつららに関しては
片方の隣のみ考える.すなわち,1 本目のつららは2 本目のつららより長けれ
ば伸び,N 本目のつららはN −1 本目のつららより長ければ伸びる).
• どのつららも,L cm(2 ≦L ≦50000)に達した瞬間に,根元から折れる(折
れたつららは,以後長さ0 cm のつららとみなす).
最初の段階で,隣り合う2 本のつららの長さはすべて異なっている.このとき,十分
な時間が経過すれば,N 本すべてのつららが折れて長さ0 cm となる.JOI 君は,つ
ららがこのような状態になるまでの時間を知りたくなった.
N 本のつららの最初の長さとつららの限界の長さL が与えられると,すべてのつ
ららが折れるまでにかかる時間を求めるプログラムを作成せよ.
入力
入力ファイルのファイル名はinput.txt である.
入力の1 行目には,つららの本数を表す整数N とつららの限界の長さを表す整数
L が,空白を区切りとしてこの順に書かれている.入力のi + 1 行目(1 ≦i ≦N) に
は,i 本目のつららの最初の長さを表す整数ai (1 ≦ai < L) が書かれている.
採点用データのうち,配点の30% 分については,N ≦500 かつL ≦1000 を満
たす.
出力
出力ファイルのファイル名はoutput.txt である.
output.txt は,すべてのつららが折れるまでにかかる時間を表す1 つの整数のみ
を含む1 行からなる.
問題3-1
入出力の例
例1 例2
input.txt input.txt
4 6 6 10
4 3
2 4
3 1
5 9
5
1
output.txt
8
output.txt
15
例1 の場合,1, 2, 3, 4 本目のつららは,それぞれ2, 8, 4, 1 時間後に折れる.した
がって,すべてのつららが折れるまでにかかる時間は8 時間であるので,8 を出力
する.
問題3-2