← 返回题目列表

AtCoder · joiopen2022_a

A. 跷跷板

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

以下是来自日本的原始新闻PDF,已完整保存和染色。

シーソー (Seesaw) - 原题 PDF 第 1 页
原题PDF第1页
シーソー (Seesaw) - 原题 PDF 第 2 页
原题PDF第2页
可复制的 PDF 提取文本
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                                  JOI Open Contest

                                                                                      July 3, 2022


                                                                              seesaw

                  シーソー(Seesaw)



 長さ109 の重さを無視できるまっすぐな棒が左右の方向に置かれており,重さ1 のおもりがN 個付いて
いる.N 個のおもりの付いている位置は相異なり,左からi 番目(1 ≦i ≦N) のおもりは左から長さAi の地

点に付いている.

 はじめに幅w の箱を用意して,棒の左から長さl 以上r 以下(0 ≦l < r ≦109) の範囲を支えるようにす

る.ただし,r = l + w を満たさなければならない.l とr はこれ以降変更することはできない.

 次に,棒についているおもりのうち,最も左にあるまたは最も右にあるおもりを一つ選び取り外す操作を

N −1 回繰り返す.このとき,初期状態と最終状態も含めて,棒に付いているおもりの重心が常に左から長

さl 以上r 以下の位置になければならない.ただし,棒にm 個のおもりが付いており,それぞれ左から長さ
b1, b2, . . . , bm の位置にあるとき,その重心は左から長さb1+b2+···+bmm  の位置になる.
 おもりの個数N とおもりの位置A1, A2, . . . , AN が与えられたとき,必要な箱の幅w の最小値を求めるプ

ログラムを作成せよ.


入力


 入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.


    N

      A1 A2 · · · AN


出力

 標準出力に,必要な箱の幅w の最小値を1 行で出力せよ.正解との相対誤差または絶対誤差が
0.000 000 001 (= 10−9) 以下であるような答えを出力すれば,正答とみなされる.出力は以下のいずれ

かの形式でなければならない.

    • 整数.(例:123,0,-2022)

    • 整数,半角ピリオド,0 から9 までの数字を並べた列,をその順にスペースなどで区切らず続けた形

    式.出力する小数点以下の桁数に制限はない.(例:123.4,-123.00,0.00288)





                       シーソー– 1 / 2

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                                  JOI Open Contest

                                                                                      July 3, 2022


                                                                              seesaw



制約

    • 2 ≦N ≦200 000.
    • 0 ≦A1 < A2 < · · · < AN ≦1 000 000 000 (= 109)


小課題

    1. (1 点) N ≦20.

    2. (33 点) N ≦100.

    3. (33 点) N ≦2 000.

    4. (33 点) 追加の制約はない.


入出力例

  入力例1              出力例1

   3                              0.8333333333

   1 2 4

 箱の幅を5 とし,l = 3  r = 7 として,以下のように操作を行えばよい.              6             2,      3

    • はじめ重心の位置は7 である.                                 3
    • 1 回目の操作では,一番右のおもり(左から長さ4 の地点にあるおもり)を取り外す.すると,重心
   の位置は3 となる.
                    2
    • 2 回目の操作では,一番左のおもり(左から長さ1 の地点にあるおもり)を取り外す.すると,重心

   の位置は2 となる.

 このとき,常に重心がl 以上r 以下の範囲にある.
   5 よりも箱の幅を小さくすることはできないため,5 を小数で表記した値を出力する.
   6                                                            6
 この入力例はすべての小課題の制約を満たす.


  入力例2              出力例2

   6                              1.166666667

   1 2 5 6 8 9

 この入力例はすべての小課題の制約を満たす.




                       シーソー– 2 / 2