← 返回题目列表

AtCoder · joigsc2022_c

C. 团队竞赛

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

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

チーム戦 (Team Contest) - 原题 PDF 第 1 页
原题PDF第1页
チーム戦 (Team Contest) - 原题 PDF 第 2 页
原题PDF第2页
チーム戦 (Team Contest) - 原题 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 – Team Contest

              チーム戦(Team Contest)



  JOI 大学にはN 匹のビーバーが在籍しており,その全員が競技プログラミングに取り組んでいる.各ビー

バーには考察力・実装力・運という3 種類の能力を表す数値が定められており,それらの値が大きいほど能
力が高いことを示す.i 匹目(1 ≦i ≦N) のビーバーの考察力はXi,実装力はYi,運はZi である.
 今年,JOI 大学のビーバーたちはチーム対抗のプログラミングコンテストに出場することになった.この

コンテストでは,3 匹でチームを組んで競技プログラミングの問題に取り組む.ここで,JOI 大学のコーチ

であるビ太郎は,チームワークを意識して,以下の条件を満たすようにN 匹の中から3 匹を選んでチーム

を組むことにした.

条件どのチームメンバーにも長所がある.すなわち,どのチームメンバーも,他の2 匹より値が真に大き

   いような能力を持っている.


 ビ太郎は,この条件を満たすなかで可能な限り総合力が高いチームを組みたいと思っている.ここで,

チームの総合力は,3 匹のチームメンバーの考察力の最大値,実装力の最大値,運の最大値の3 つの値の合

計として計算される.

 各ビーバーの能力の情報が与えられたとき,条件を満たすチームを作ることが可能か判定し,もし可能な

らばチームの総合力として考えられる最大の値を求めるプログラムを作成せよ.


入力


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


    N

      X1 Y1 Z1
      X2 Y2 Z2
                                 ...

     XN YN ZN


出力

 標準出力に,チームの総合力として考えられる最大の値を1 行で出力せよ.ただし,問題文中の条件を満

たすようにチームを組むことが不可能な場合は,-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 – Team Contest



制約

    • 3 ≦N ≦150 000.
    • 1 ≦Xi ≦100 000 000 (= 108) (1 ≦i ≦N).
    • 1 ≦Yi ≦100 000 000 (= 108) (1 ≦i ≦N).
    • 1 ≦Zi ≦100 000 000 (= 108) (1 ≦i ≦N).


小課題

    1. (8 点) N ≦300.

    2. (29 点) N ≦4 000.
    3. (9 点) Xi ≦5,Yi ≦5,Zi ≦5 (1 ≦i ≦N).
    4. (9 点) Xi ≦20,Yi ≦20,Zi ≦20 (1 ≦i ≦N).
    5. (9 点) Xi ≦300,Yi ≦300,Zi ≦300 (1 ≦i ≦N).
    6. (9 点) Xi ≦4 000,Yi ≦4 000,Zi ≦4 000 (1 ≦i ≦N).
    7. (27 点) 追加の制約はない.


入出力例

  入力例1              出力例1

   5                              13

   3 1 4

   2 3 1

   1 5 5

   4 4 2

   5 2 3

  1, 4, 5 匹目のビーバーでチームを組むと,以下のように問題文中の条件を満たす.

    • 1 匹目のビーバーは他の2 匹よりも運の値が大きい.

    • 4 匹目のビーバーは他の2 匹よりも実装力の値が大きい.

    • 5 匹目のビーバーは他の2 匹よりも考察力の値が大きい.

 このとき,チームメンバーの考察力・実装力・運の最大値はそれぞれ5, 4, 4 であるため,チームの総合力

は13 である.総合力を14 以上にするチームの組み方は存在しないので,13 を出力する.



                       チーム戦– 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 – Team Contest


 なお,例えば1, 3, 5 匹目のビーバーでチームを組むと,チームの総合力は15 となるものの,1 匹目の

ビーバーには他のメンバーよりも値が真に大きい能力がないため,問題文中の条件を満たさないことに注意

せよ.

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


  入力例2              出力例2

   8                              15

   1 1 1

   1 1 5

   1 5 1

   5 1 1

   1 5 5

   5 1 5

   5 5 1

   5 5 5

  2, 3, 4 匹目のビーバーでチームを組むと,問題文中の条件を満たし,チームの総合力は15 となる.総合

力を16 以上にするチームの組み方は存在しないので,15 を出力する.

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


  入力例3              出力例3

   4                              -1

   1 2 3

   1 2 3

   1 2 3

   1 2 3

 問題文中の条件を満たすようにチームを組むことはできない.よって-1 を出力する.

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





                       チーム戦– 3 / 3