← 返回题目列表

AtCoder · joigsc2022_a

A. 接力赛(Relay)

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

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

リレー競技 (Relay) - 原题 PDF 第 1 页
原题PDF第1页
リレー競技 (Relay) - 原题 PDF 第 2 页
原题PDF第2页
リレー競技 (Relay) - 原题 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 1 – Relay

                 リレー競技(Relay)



  JOI 高校の陸上部にはN 人の部員がおり,1 からN までの番号が付けられている.部員i (1 ≦i ≦N) の
100 m 走のタイムはAi ミリ秒であり,バトンパスの速さはBi である.
 さて,この陸上部は300 m リレーの全国大会に出場することになった.300 m リレーは,3 人の走者がバ

トンを渡しながら100 m ずつ走る競技である.具体的には,第1 走者が部員i (1 ≦i ≦N),第2 走者が部員

 j (1 ≦j ≦N),第3 走者が部員k (1 ≦k ≦N) であるとき,以下の手順で行われる.

    1. 部員i がバトンを持って100 m 走る.これにはAi ミリ秒かかる.
    2. 部員i から部員j にバトンを渡す.これにはmax(Bi, Bj) ミリ秒かかる.
    3. 部員j がバトンを持って100 m 走る.これにはAj ミリ秒かかる.
    4. 部員j から部員k にバトンを渡す.これにはmax(Bj, Bk) ミリ秒かかる.
    5. 部員k がバトンを持って100 m 走る.これにはAk ミリ秒かかる.

 すなわち,300m リレーの記録はAi +max(Bi, Bj)+A j +max(Bj, Bk)+Ak ミリ秒となる.ここで,max(x, y)
はx とy のうち小さくない方の数とする.あなたは陸上部の顧問であるため,この記録ができるだけ短くな

るように3 人の異なる部員を選び,その走順を決めなければならない.

 陸上部のN 人の部員の情報が与えられたとき,300 m リレーの記録として考えられる最小値を求めるプ

ログラムを作成せよ.


入力


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


    N

      A1 B1
      A2 B2
                                 ...

     AN BN


出力

 標準出力に,300 m リレーの記録として考えられる最小値をミリ秒単位で表す整数を1 行で出力せよ.





                      リレー競技– 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 1 – Relay



制約

    • 3 ≦N ≦200 000.
    • 1 ≦Ai ≦100 000 000 (= 108) (1 ≦i ≦N).
    • 1 ≦Bi ≦100 000 000 (= 108) (1 ≦i ≦N).


小課題

    1. (25 点) N ≦100.

    2. (33 点) N ≦3 000.
    3. (10 点) A1 = A2 = · · · = AN.
    4. (32 点) 追加の制約はない.


入出力例

  入力例1              出力例1

   4                              3320

   1070 90

   1080 70

   1050 60

   1020 100

 第1 走者に部員4,第2 走者に部員3,第3 走者に部員2 を選ぶと,手順1, 2, 3, 4, 5 にはそれぞれ

1020, 100, 1050, 70, 1080 ミリ秒かかるため,300 m リレーの記録は1020 + 100 + 1050 + 70 + 1080 = 3320

ミリ秒となる.これより記録を短くすることはできないため,3320 を出力する.

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


  入力例2              出力例2

   5                              3034

   1000 28

   1000 14

   1000 21

   1000 20

   1000 14



                      リレー競技– 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 1 – Relay




 第1 走者に部員2,第2 走者に部員5,第3 走者に部員4 を選ぶと,手順1, 2, 3, 4, 5 にはそれぞれ

1000, 14, 1000, 20, 1000 ミリ秒かかるため,300 m リレーの記録は1000 + 14 + 1000 + 20 + 1000 = 3034 ミ

リ秒となる.これより記録を短くすることはできないため,3034 を出力する.

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


  入力例3              出力例3

   9                              13

   3 1

   4 1

   5 9

   2 6

   5 3

   5 8

   9 7

   9 3

   2 3

 第1 走者に部員1,第2 走者に部員2,第3 走者に部員9 を選ぶと,手順1, 2, 3, 4, 5 にはそれぞれ

3, 1, 4, 3, 2 ミリ秒かかるため,300 m リレーの記録は3 + 1 + 4 + 3 + 2 = 13 ミリ秒となる.これより記録を

短くすることはできないため,13 を出力する.

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





                      リレー競技– 3 / 3