← 返回题目列表

AtCoder · joigsc2022_e

E. 运送瓜类(Melons)

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

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

メロンの出荷 (Melons) - 原题 PDF 第 1 页
原题PDF第1页
メロンの出荷 (Melons) - 原题 PDF 第 2 页
原题PDF第2页
メロンの出荷 (Melons) - 原题 PDF 第 3 页
原题PDF第3页
可复制的 PDF 提取文本
The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                             Contest 2 – Melons

                メロンの出荷(Melons)



  EGOI 農場はメロンの入荷と出荷を行っており,今朝N 個のメロンを入荷した.メロンには入荷した順
に1 からN までの番号が付けられており,メロンi (1 ≦i ≦N) の重さはAi である.
  EGOI 農場で働く理恵さんは,メロンの箱詰めを担当している.今から,EGOI 農場で整数x (1 ≦x ≦N)

が決定される.その後,理恵さんにはメロンx, x + 1, . . . , N がこの順に渡され,以下を繰り返して箱詰めを

行うことになっている.

    • 空の箱を用意し,その箱に渡されたメロンを入れ続ける.ただし,渡されたメロンを入れたらその箱

   に入っているメロンの重さの合計がL を超えてしまう場合は,そのメロンを入れずに箱を出荷する.

   (そのメロンは次の箱に入れることになる.)

 メロンN を箱に入れたら,その箱を出荷して理恵さんの作業は終了する.

 理恵さんはx がどの値に決定されても大丈夫なように準備をしたいと思った.入荷するメロンの情報と

箱の重量制限L が与えられるので,すべてのx の場合について,出荷する箱の個数と,最後に出荷する箱に

入れるメロンの重さの合計を求めるプログラムを作成せよ.


入力


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


    N L

      A1
      A2
                                 ...

     AN


出力

 標準出力にN 行で出力せよ.i 行目(1 ≦i ≦N) には,x = i の場合について,出荷する箱の個数と最後に

出荷する箱に入れるメロンの重さの合計をこの順に空白区切りで出力せよ.





                     メロンの出荷– 1 / 3

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                             Contest 2 – Melons



制約

    • 1 ≦N ≦200 000.
    • 1 ≦L ≦1 000 000 000 (= 109).
    • 1 ≦Ai ≦L (1 ≦i ≦N).


小課題

    1. (6 点) A1 = A2 = · · · = AN.
    2. (21 点) N ≦1 000.

    3. (29 点) どのx に対しても,理恵さんが出荷する箱の数は10 個以下になる.

    4. (33 点) どのx に対しても,理恵さんが1 つの箱に入れるメロンの個数は10 個以下になる.

    5. (11 点) 追加の制約はない.


入出力例

  入力例1              出力例1

   7 100                          4 10

   20                             4 10

   80                             3 10

   50                             2 90

   40                             2 10

   20                             1 90

   80                             1 10

   10

 例えばx = 1 の場合,理恵さんは以下のように箱詰めを行うことになる.

    1. メロン1 を箱に入れる.箱のメロンの重さの合計は20 となる.

    2. メロン2 を箱に入れる.箱のメロンの重さの合計は100 となる.

    3. もしメロン3 を箱に入れたら,箱のメロンの重さの合計は150 となってしまう.そのため,現在の

   箱を出荷し,メロン3 は新しい箱に入れる.新しい箱のメロンの重さの合計は50 となる.

    4. メロン4 を箱に入れる.箱のメロンの重さの合計は90 となる.

    5. もしメロン5 を箱に入れたら,箱のメロンの重さの合計は110 となってしまう.そのため,現在の




                     メロンの出荷– 2 / 3

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                             Contest 2 – Melons


   箱を出荷し,メロン5 は新しい箱に入れる.新しい箱のメロンの重さの合計は20 となる.

    6. メロン6 を箱に入れる.箱のメロンの重さの合計は100 となる.

    7. もしメロン7 を箱に入れたら,箱のメロンの重さの合計は110 となってしまう.そのため,現在の

   箱を出荷し,メロン7 は新しい箱に入れる.新しい箱のメロンの重さの合計は10 となる.

    8. 最後に現在の箱を出荷する.

 そのため,x = 1 の場合,出荷する箱の個数は4 個であり,最後の箱に入れるメロンの重さの合計は10 と

なる.したがって,1 行目には4 と10 をこの順に空白区切りで出力する.

 この入力例は小課題2, 3, 4, 5 の制約を満たす.


  入力例2              出力例2

   6 160                          3 126

   63                             3 63

   63                             2 126

   63                             2 63

   63                             1 126

   63                             1 63

   63

 例えばx = 1 の場合,最初の箱にはメロン1, 2 を入れ,次の箱にはメロン3, 4 を入れ,その次の箱にはメ

ロン5, 6 を入れることになる.そのため,出荷する箱の個数は3 個であり,最後に出荷する箱に入れるメロ

ンの重さの合計は126 となる.したがって,1 行目には3 と126 をこの順に空白区切りで出力する.

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


  入力例3              出力例3

   5 20                           2 18

   7                              2 8

   10                             1 18

   4                              1 14

   6                              1 8

   8

 例えばx = 2 の場合,最初の箱にはメロン2, 3, 4 を入れ,次の箱にはメロン5 のみを入れることになる.

そのため,出荷する箱の個数は2 個であり,最後に出荷する箱に入れるメロンの重さの合計は8 となる.し

たがって,2 行目には2 と8 をこの順に空白区切りで出力する.

 この入力例は小課題2, 3, 4, 5 の制約を満たす.




                     メロンの出荷– 3 / 3