← 返回题目列表

AtCoder · joi2010ho_c

C. 冰柱

中文机器翻译题面 查看原题

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

つらら - 原题 PDF 第 1 页
原题PDF第7页
つらら - 原题 PDF 第 2 页
原题PDF第8页
可复制的 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