← 返回题目列表

AtCoder · joisc2012_invitation

invitation. 邀请

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

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

招待 - 原题 PDF 第 1 页
原题PDF第7页
招待 - 原题 PDF 第 2 页
原题PDF第8页
招待 - 原题 PDF 第 3 页
原题PDF第9页
可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2011/2012
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                         Contest Day 4 – Invitation

                           招待(Invitation)



  20XX 年,ついにIOI がJOI 国のJOI 町で行われることになり,これを記念してパーティーが開かれるこ
とになった.JOI 町にはA 匹の犬(1, 2, . . . , A の番号がついている) とB 匹の猫(1, 2, . . . , B の番号がついて
いる) がいる.あなたはこのA + B 匹みんなをパーティーに招待しようと考えた.
 犬たちと猫たちの間には,N 個の仲良しグループがある.i 番目の仲良しグループは番号がPi 以上Qi 以
下の犬たちQi −Pi + 1 匹と番号がRi 以上S                                                                                            i 以下の猫たちS i −Ri + 1 匹からなる.また,各仲良しグルー
プには仲良し度と呼ばれる正の整数が定まっている.i 番目の仲良しグループの仲良し度はTi である.1 匹
の犬や1 匹の猫が複数の仲良しグループに所属しているかもしれないし,どの仲良しグループにも所属し
ていない犬や猫がいるかもしれない.
 あなたは番号C の犬と非常に仲が良く,その犬の招待に既に成功した.あなたは以下の行動を繰り返し
て残りの犬たちと猫たちを招待することにした.

   • A + B 匹みんなを既に招待できていれば終了する.
   • まだ誘えていない犬または猫それぞれに対して,誘うときの幸せ値を考える.幸せ値とは,その犬ま
   たは猫が所属している仲良しグループであって,既に招待することに成功した犬または猫が1 匹以上
   所属しているもののうちの,最大の仲良し度である.そのような仲良しグループが存在しない場合は
   幸せ値は0 となる.

   • 幸せ値が最大の犬または猫を選ぶ.そのような犬または猫が複数いる場合は,犬を優先し,それでも
     1 匹に定まらない場合は,番号が小さい方を優先する.

   • 選ばれた犬または猫の幸せ値が0 ならば,招待は失敗して終了する.そうでなければ,選ばれた犬ま
   たは猫を招待することに成功する.

 あなたは,この招待方法がどういう結果になるのかを前もって計算することにした.


課題

 犬の数A,猫の数B,あなたと非常に仲が良い犬の番号C,およびN 個の仲良しグループの情報が与え
られたとき,A + B 匹みんなを招待することに成功するかどうかを判定し,また,成功する場合は,各ス
テップで選ばれる犬または猫の幸せ値の合計がいくつになるかを求めるプログラムを作成せよ.


制限

   1 ≦A ≦1 000 000 000 犬の数
   1 ≦B ≦1 000 000 000 猫の数
   1 ≦N ≦100 000    仲良しグループの個数
   1 ≦Ti ≦1 000 000 000 仲良し度


                         招待– 1 / 3

Japanese Olympiad in Informatics 2011/2012
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                         Contest Day 4 – Invitation


入力

 標準入力から以下の入力を読み込め.

   • 1 行目には整数A, B, C (1 ≦C ≦A) が空白を区切りとして書かれており,それぞれ犬の数,猫の数,
   あなたと非常に仲が良い犬の番号を表す.

   • 2 行目には整数N が書かれており,仲良しグループの個数を表す.
                                                                                                                                                                           i ≦B) が空白を区切りと   • 2 + i 行目(1 ≦i ≦N) には整数Pi, Qi, Ri, S i, Ti (1 ≦Pi ≦Qi ≦A, 1 ≦Ri ≦S
   して書かれており,i 番目の仲良しグループは番号がPi 以上Qi 以下の犬たちと番号がRi 以上S i 以
   下の猫たちからなり,仲良し度がTi であることを表す.


出力

 標準出力に,次に示される整数1 つを1 行で出力せよ.

   • A + B 匹みんなを招待することに成功する場合,各ステップで選ばれる犬または猫の幸せ値の合計を
   表す整数.

   • 招待が途中で失敗する場合,整数−1.


採点基準

 採点用データのうち,配点の30%分については,A ≦1 000,B ≦1 000,N ≦2 000 を満たす.
 採点用データのうち,配点の50%分については,N ≦2 000 を満たす.


入出力例

  入力例1        出力例1
   5 6 3                280
   4
   2 4 1 3 20
   1 2 2 4 40
   4 5 2 3 30
   4 4 4 6 10

 この例では,犬たちと猫たちは次のように招待される.

   • あなたは番号3 の犬(以下「犬3」のように呼ぶ) の招待に既に成功している.
   • 幸せ値を計算すると,犬2:20,犬4:20,猫1:20,猫2:20,猫3:20,他の招待されていない犬
   や猫:0 である.あなたは犬2 を選び,招待に成功する.


                         招待– 2 / 3

Japanese Olympiad in Informatics 2011/2012
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                         Contest Day 4 – Invitation

   • 幸せ値を計算すると,犬1:40,犬4:20,猫1:20,猫2:40,猫3:40,猫4:40,他の招待され
   ていない犬や猫:0 である.あなたは犬1 を選び,招待に成功する.

   • 以下同様に招待を続けると,以下の表の順番ですべての犬と猫が招待される.

                   動物 番号 幸せ値
                   犬     3   —
                   犬     2      20
                   犬     1      40
                   猫     2      40
                   猫     3      40
                   猫     4      40
                   犬     4      30
                   犬     5      30
                   猫     1      20
                   猫     5      10
                   猫     6      10

 表の「幸せ値」の列の値は,その犬または猫を誘うときの幸せ値を表している.これらの合計である280
を出力する.

  入力例2        出力例2
   10 10 1              -1
   2
   1 5 1 5 3
   6 10 6 10 4

 この例では,犬1,犬2,犬3,犬4,犬5,猫1,猫2,猫3,猫4,猫5 の10 匹の招待の後に選ばれる
犬6 は幸せ値0 であるため,招待は途中で失敗する.





                         招待– 3 / 3