← 返回题目列表

AtCoder · joisc2020_b

B. 美味可口的汉堡牛排(Hamburg Steak)

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

以下是来自日本的官方日本新闻原版PDF,已完整保留并按原样染色。

美味しい美味しいハンバーグ (Hamburg Steak) - 原题 PDF 第 1 页
原题PDF第1页
美味しい美味しいハンバーグ (Hamburg Steak) - 原题 PDF 第 2 页
原题PDF第2页
美味しい美味しいハンバーグ (Hamburg Steak) - 原题 PDF 第 3 页
原题PDF第3页
可复制的 PDF 提取文本
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                                 Contest Day 1 – Hamburg Steak

       美味しい美味しいハンバーグ(Hamburg Steak)



 あなたはJust Odd Inventions 社を知っているだろうか? この会社の業務は「ただ奇妙な発明(just odd

inventions)」をすることである.ここでは略してJOI 社と呼ぶ.

 今はJOI 社の新年会で,広大な金網の上でN 枚のハンバーグを焼いている.ここでは金網は縦と横が共に

1 000 000 000 マスの2 次元のマス目として扱う.左からx 番目,下からy 番目のマス(1 ≦x ≦1 000 000 000,

1 ≦y ≦1 000 000 000) を(x, y) と表すことにする.
 ハンバーグには1 からN までの番号が付いており,ハンバーグi (1 ≦i ≦N) は,マス(Li, Di) を左下,マ
ス(Ri, Ui) を右上とする長方形領域にある.なお,ハンバーグ同士が重なっていることもあり得る.
  JOI 社の新入社員であるあなたの仕事は,鉄板上のK 個のマスを選び,それらのマスの中心に竹串を金網

と垂直に刺すことによって,すべてのハンバーグの焼き加減を確認することである.各ハンバーグの焼き加

減は,その上の1 個以上のマスに竹串を刺すことで確認することができる.同じマスに複数の竹串を刺して

もよいし,ハンバーグのないマスに竹串を刺してもよい.

 すなわち,あなたの仕事は以下の条件を満たす,相異なるとは限らないK 個の整数対(x1, y1), . . . , (xK, yK)
を,1 組探すことである:

    • すべてのi (1 ≦i ≦N) について,Li ≦xj ≦Ri かつDi ≦yj ≦Ui を満たすj (1 ≦j ≦K) が存在する.
    • すべてのj (1 ≦j ≦K) について,1 ≦xj ≦1 000 000 000 かつ1 ≦yj ≦1 000 000 000 である.

 ハンバーグの位置と竹串の本数が与えられたとき,竹串の刺し方を1 つ求めるプログラムを作成せよ.た

だしこの問題では,上の条件を満たすマスの組が存在するような入力のみが与えられる.


入力


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


    N K

      L1 D1 R1 U1
      L2 D2 R2 U2
                                 ...

     LN DN RN UN


出力

 標準出力にK 行で出力せよ.j 行目(1 ≦j ≦K) 行目には,xj, y j を空白区切りで出力せよ.



                 美味しい美味しいハンバーグ– 1 / 3

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                                 Contest Day 1 – Hamburg Steak



 条件を満たす竹串の刺し方が複数存在する場合は,どれを出力してもよい.


制約

    • 1 ≦N ≦200 000.

    • 1 ≦K ≦4.
    • 1 ≦Li ≦Ri ≦1 000 000 000 (1 ≦i ≦N).
    • 1 ≦Di ≦Ui ≦1 000 000 000 (1 ≦i ≦N).
    • 問題文の条件を満たすK 個のマスの組が存在する.


小課題

    1. (1 点) N ≦2000,K = 1.

    2. (1 点) N ≦2000,K = 2.

    3. (3 点) N ≦2000,K = 3.

    4. (6 点) N ≦2000,K = 4.

    5. (1 点) K = 1.

    6. (3 点) K = 2.

    7. (6 点) K = 3.

    8. (79 点) K = 4.





                 美味しい美味しいハンバーグ– 2 / 3

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                                 Contest Day 1 – Hamburg Steak



入出力例

  入力例1              出力例1

   4 2                            2 2

   2 1 3 3                        7 4

   1 2 4 3

   6 1 7 4

   5 3 7 5

 マス(2, 2) に竹串を刺すことでハンバーグ1, 2 の焼き加減を確認することができ,マス(7, 4) に竹串を刺

すことでハンバーグ3, 4 の焼き加減を確認することができる.

   (2, 2) と(7, 4) 以外にも,(3, 3) と(6, 4) なども条件を満たす.


  入力例2              出力例2

   3 3                            1 1

   1 1 1 1                        1 2

   1 2 1 2                        1 3

   1 3 1 3





                 美味しい美味しいハンバーグ– 3 / 3