← 返回题目列表

AtCoder · joigsc2022_f

F. 机场

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

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

空港 (Airport) - 原题 PDF 第 1 页
原题PDF第1页
空港 (Airport) - 原题 PDF 第 2 页
原题PDF第2页
空港 (Airport) - 原题 PDF 第 3 页
原题PDF第3页
空港 (Airport) - 原题 PDF 第 4 页
原题PDF第4页
可复制的 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 – Airport

                       空港(Airport)



  EGOI 空港にはN 本の滑走路があり,1 からN までの番号が付けられている.この空港では,飛行機の

離陸開始から終了までK 分かかり,着陸開始から終了までL 分かかる.この連続するK 分またはL 分の

間,飛行機は1 つの滑走路を占有することになる.

  EGOI 空港で働いているJOI 君は,あるT 分間の期間における離着陸のスケジュールを立てる仕事を任

された.期間の開始時刻を時刻0 とし,時刻0 からt 分経過した時刻を時刻t と表す.期間が終わるのは時

刻T である.

 期間中に着陸するのは,1 からM まで番号付けられたM 機の飛行機である.飛行機i (1 ≦i ≦M) は時刻
Ai に着陸を開始することが決まっているが,使用する滑走路はこれからJOI 君が決めることになっている.

また,離陸のスケジュールは全く決められていないため,離陸する飛行機の数,各飛行機の離陸開始時刻と

使用する滑走路はすべてJOI 君が決めることになる.

 以上を踏まえて,スケジュールは以下のルールをすべて守るように作らなければならない.

    • 1 つの滑走路で複数の飛行機が同時に離着陸を行っている状態にしてはならない.ただし,ある飛行

   機が離着陸を終えると同時に,同じ滑走路で別の飛行機が離着陸を開始することは許される.

    • すべての離着陸はT 分間の期間中に行われなければならない.すなわち,時刻0 より前に離着陸を

   開始したり,時刻T より後に離着陸を終了したりしてはならない.

  JOI 君はこのルールをすべて守ったうえで,できるだけ多くの飛行機が離陸できるようなスケジュールを

立てたいと思った.

 滑走路の数,着陸する飛行機の数,期間の長さ,離陸にかかる時間,着陸にかかる時間,各飛行機が着陸

を開始する時刻が与えられたとき,期間中にEGOI 空港を離陸できる飛行機の数の最大値を求めるプログラ

ムを作成せよ.ただし,ルールをすべて守ったスケジュールを作ることが不可能である場合は,そのことを

報告せよ.





                          空港– 1 / 4

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

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                             Contest 2 – Airport



入力


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


    N M T K L

      A1 A2 · · · AM


出力

 標準出力に,期間中にEGOI 空港を離陸できる飛行機の数の最大値を1 行で出力せよ.ただし,ルールを

すべて守ったスケジュールを作ることが不可能である場合は,-1 を出力せよ.


制約

    • 1 ≦N ≦100 000.

    • 1 ≦M ≦100 000.
    • 1 ≦T ≦1 000 000 000 (= 109).

    • 1 ≦K ≦T.

    • 1 ≦L ≦T.
    • 0 ≦Ai ≦T −L (1 ≦i ≦M).


小課題

    1. (7 点) N = 1.

    2. (12 点) N = 2,M ≦20.

    3. (17 点) N = 2,K = 2,L = 2.

    4. (28 点) N = 2.

    5. (11 点) N ≦100.

    6. (25 点) 追加の制約はない.





                          空港– 2 / 4

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

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                             Contest 2 – Airport



入出力例

  入力例1              出力例1

   2 4 15 3 2                     5

   4 1 5 12

 例えば,以下のようなスケジュールを立てることで,5 機の飛行機が離陸することができる.

    1. 時刻0 に,滑走路1 で飛行機の離陸を開始する.

    2. 時刻1 に,滑走路2 で飛行機2 の着陸を開始する.

    3. 時刻4 に,滑走路2 で飛行機1 の着陸を開始する.

    4. 時刻5 に,滑走路1 で飛行機3 の着陸を開始する.

    5. 時刻6 に,滑走路2 で飛行機の離陸を開始する.

    6. 時刻7 に,滑走路1 で飛行機の離陸を開始する.

    7. 時刻9 に,滑走路2 で飛行機の離陸を開始する.

    8. 時刻10 に,滑走路1 で飛行機の離陸を開始する.

    9. 時刻12 に,滑走路2 で飛行機4 の着陸を開始する.

 どのようなスケジュールを立てても,ルールをすべて守ったうえで6 機以上が離陸することはできないた

め,5 を出力する.

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


  入力例2              出力例2

   2 6 23 3 6                     -1

   9 13 1 16 4 8

 ルールをすべて守ったスケジュールを作ることが不可能であるため,-1 を出力する.

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


  入力例3              出力例3

   1 5 20 2 1                     7

   2 8 11 15 5

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





                          空港– 3 / 4

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

                                                       Spring Training Camp/Qualifying Trial

                                                March 20–23, 2022 (Komaba, Tokyo)


                                                                           Contest 2 – Airport


 入力例4              出力例4

 2 6 13 2 2                     5

 7 0 1 10 7 4

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


 入力例5              出力例5

 4 4 14 2 3                     21

 5 6 3 9

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


 入力例6                          出力例6

 8 15 100 4 7                                      170

 93 10 74 46 37 64 68 5 38 67 6 48 76 36 21

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





                        空港– 4 / 4