← 返回题目列表

AtCoder · joiopen2024_b

B. 中暑

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

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

熱中症 (Heat Stroke) - 原题 PDF 第 1 页
原题PDF第1页
熱中症 (Heat Stroke) - 原题 PDF 第 2 页
原题PDF第2页
熱中症 (Heat Stroke) - 原题 PDF 第 3 页
原题PDF第3页
熱中症 (Heat Stroke) - 原题 PDF 第 4 页
原题PDF第4页
可复制的 PDF 提取文本
The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)

                                                                  JOI Open Contest

                                                                            June 16, 2024


                                                                                heat

                熱中症(Heat Stroke)



  JOI 島は東西一列に並んだL 個の地区からなり,各地区は西から順に1 からL までの番号が付けられて

いる.また,JOI 島にはL −1 本の道路があり,具体的には各1 ≦i ≦L −1 について,地区i と地区i + 1 を

双方向に結ぶ道路がある.ここで,地区i と地区i + 1 を結ぶ道路は,道路i と呼ばれている.


           道路1       道路2
      地区1       地区2       地区3        …     地区𝐿



 さて,20XX 年,国際情報オリンピックがJOI 島で開催されることになった.JOI 島は酷暑で有名な島で

あるため,暑さに慣れていない海外の選手にとって,熱中症のリスクが高い.そこで国際情報オリンピック

の運営は,次のような対策を立てることにした.

    • 各地区i (1 ≦i ≦L) に,Ci 人が入院できる病院を準備する.ただしCi = 0 の場合もある.
    • 国際情報オリンピックの開催期間中,道路x (1 ≦x ≦L −1) 上で熱中症患者が発生した場合,次のよ

   うな手順にしたがって患者を搬送し,入院させる.

       – その時点で,地区x の病院と地区x + 1 の病院のうち入院できる方に救急車で搬送し,入院させ

     る.両方に入院できる場合はどちらに搬送される可能性もある.どちらの病院にも入院できない

     場合は,ドクターヘリで島外の総合病院に搬送し,入院させる.


 しかし,ドクターヘリでの搬送は費用がかかるため,運営は最大何人の患者がドクターヘリで搬送される

かを知りたい.そこで1 つのシナリオとして,以下を考える.

    • 国際情報オリンピックが始まった時点では,どの病院にも入院患者がいない.

    • 国際情報オリンピックの開催期間中,合計N 人の熱中症患者が発生する.j 番目(1 ≦j ≦N) の患者
    は道路Xj 上で熱中症になる.
    • 各1 ≦j ≦N −1 について,j + 1 番目の患者が熱中症になった時点では,j 番目までの患者は既に入

   院している.また,熱中症患者はみな重症であるため,開催期間中に退院することはない.


 地区の数,病院および熱中症患者に関する情報が与えられたとき,上記のシナリオにおいて,最大何人の

患者がドクターヘリで搬送されるかを求めるプログラムを作成せよ.





                        熱中症– 1 / 4

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)

                                                                  JOI Open Contest

                                                                            June 16, 2024


                                                                                heat



入力


 入力は以下の形式で標準入力から与えられる.


     L

     C1 C2 · · · CL

    N

      X1 X2 · · · XN


出力

 標準出力に,最大何人の患者がドクターヘリで搬送されるかを1 行で出力せよ.


制約

    • 2 ≦L ≦8 000.
    • 0 ≦Ci ≦8 000 (1 ≦i ≦L).
    • 1 ≦N ≦8 000.
    • 1 ≦X j ≦L −1 (1 ≦j ≦N).
    • 入力される値はすべて整数である.


小課題

    1. (6 点) X1 ≦X2 ≦· · · ≦XN.
    2. (7 点) L ≦18,N ≦18,Ci = 1 (1 ≦i ≦L).
    3. (7 点) L ≦18,N ≦100,Ci = 1 (1 ≦i ≦L).
    4. (25 点) L ≦100,N ≦100,Ci = 1 (1 ≦i ≦L).
    5. (25 点) L ≦100,N ≦100.

    6. (10 点) L ≦600,N ≦600.

    7. (15 点) L ≦3 500,N ≦3 500.

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





                        熱中症– 2 / 4

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)

                                                                  JOI Open Contest

                                                                            June 16, 2024


                                                                                heat



入出力例

  入力例1              出力例1

   3                              1

   1 1 1

   3

   1 2 2

 以下のようなケースの場合,1 人の患者がドクターヘリで搬送される.

    1. 1 番目の患者を地区2 の病院に搬送し,入院させる.地区1, 2, 3 の病院における入院者数が0, 1, 0 人

   になる.

    2. 2 番目の患者を地区3 の病院に搬送し,入院させる.地区1, 2, 3 の病院における入院者数が0, 1, 1 人

   になる.

    3. 3 番目の患者については,地区2 と地区3 の両方の病院が既に入院できない状態になっているため,

   ドクターヘリで搬送し,入院させる.

  2 人以上の患者がドクターヘリで搬送されるようなケースはないため,1 を出力する.

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


  入力例2              出力例2

   6                              3

   1 1 1 1 1 1

   7

   1 3 5 4 2 2 3

 以下のようなケースの場合,3 人の患者がドクターヘリで搬送される.

    1. 1 番目の患者を地区2 の病院に搬送し,入院させる.地区1, 2, 3, 4, 5, 6 の病院における入院者数が

       0, 1, 0, 0, 0, 0 人になる.

    2. 2 番目の患者を地区4 の病院に搬送し,入院させる.地区1, 2, 3, 4, 5, 6 の病院における入院者数が

       0, 1, 0, 1, 0, 0 人になる.

    3. 3 番目の患者を地区5 の病院に搬送し,入院させる.地区1, 2, 3, 4, 5, 6 の病院における入院者数が

       0, 1, 0, 1, 1, 0 人になる.

    4. 4 番目の患者については,地区4 と地区5 の両方の病院が既に入院できない状態になっているため,

   ドクターヘリで搬送し,入院させる.





                        熱中症– 3 / 4

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)

                                                                JOI Open Contest

                                                                          June 16, 2024


                                                                               heat


  5. 5 番目の患者を地区3 の病院に搬送し,入院させる.地区1, 2, 3, 4, 5, 6 の病院における入院者数が

     0, 1, 1, 1, 1, 0 人になる.

  6. 6 番目の患者については,地区2 と地区3 の両方の病院が既に入院できない状態になっているため,

  ドクターヘリで搬送し,入院させる.

  7. 7 番目の患者については,地区3 と地区4 の両方の病院が既に入院できない状態になっているため,

  ドクターヘリで搬送し,入院させる.

4 人以上の患者がドクターヘリで搬送されるようなケースはないため,3 を出力する.

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


 入力例3              出力例3

 6                              1

 4000 1 1 0 4000 1

 5

 1 1 2 3 5

この入力例は小課題1, 5, 6, 7, 8 の制約を満たす.


 入力例4              出力例4

 5                              2

 1 2 2 2 1

 8

 2 3 2 1 4 1 2 3

この入力例は小課題5, 6, 7, 8 の制約を満たす.


 入力例5                    出力例5

 10                                      3

 2 2 2 2 2 2 2 2 2 2

 18

 1 3 5 7 9 2 4 6 8 1 3 5 7 9 2 4 6 8

この入力例は小課題5, 6, 7, 8 の制約を満たす.





                       熱中症– 4 / 4