← 返回题目列表

AtCoder · joiopen2023_c

C. 花园

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

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

庭園 (Garden) - 原题 PDF 第 1 页
原题PDF第1页
庭園 (Garden) - 原题 PDF 第 2 页
原题PDF第2页
庭園 (Garden) - 原题 PDF 第 3 页
原题PDF第3页
庭園 (Garden) - 原题 PDF 第 4 页
原题PDF第4页
可复制的 PDF 提取文本
The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)

                                                                  JOI Open Contest

                                                                            August 5, 2023


                                                                              garden

                    庭園(Garden)



  JOI 王国は,果てしなく広がる領地を持つ不思議な王国である.国王であるJOI 君は,領地の一部を切り

取って自分の庭にしようと考えている.

  JOI 王国の領地は十分に広い2 次元のグリッドとして表される.このグリッドは上下左右の方向に正方形

のマスが敷き詰められたものであり,ある基準となるマスから右方向にx 回,上方向にy 回進んだ場所にあ

るマスを(x, y) と表す.ただし,左方向にa 回進むことは,右方向に−a 回進むことと等しいものとする.

同様に,下方向にa 回進むことは,上方向に−a 回進むことと等しいものとする.領地にはいくつかの種類

のオブジェが置かれていて,これらのオブジェはその置かれ方によってタイプA とタイプB に分別される.

    • タイプA のオブジェは全部でN 種類あり,i 種類目(1 ≦i ≦N) のオブジェは,(Pi + kD, Qi + lD)
    (k, l は整数)と表されるようなすべてのマスに1 つずつ置かれている.
    • タイプB のオブジェは全部でM 種類あり,j 種類目(1 ≦j ≦M) のオブジェは,(R j + kD, y)(k, y は
   整数)と表されるか(x, S j + lD)(l, x は整数)と表されるようなすべてのマスに1 つずつ置かれて

   いる.

 なお,1 つのマスに複数の種類のオブジェが置かれているかもしれないことに注意せよ.

  JOI 君は,グリッド上の長方形領域を1 つ選んで庭にしようと考えている.すなわち,4 つの整数a, b, c, d

を選んだ上で,a ≦x ≦b, c ≦y ≦d を満たす整数x, y を用いて(x, y) と表されるマス全体をJOI 君の庭とす

る.JOI 君はさまざまなオブジェを眺めるのが好きなので,N + M 種類あるオブジェのいずれについても,

その種類のオブジェが1 つ以上JOI 君の庭に置かれていなければならない.あまり大きい庭を作ってしま

うと国民に怒られてしまうかもしれないので,JOI 君はそのような条件の下で含まれるマスの個数ができる

だけ少ない庭を作ろうと考えている.

 オブジェの情報が与えられたとき,JOI 君の庭を構成するマスの個数の最小値を求めるプログラムを作成

せよ.





                          庭園– 1 / 4

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)

                                                                  JOI Open Contest

                                                                            August 5, 2023


                                                                              garden



入力


 入力は以下の形式で標準入力から与えられる.


    N M D

      P1 Q1
      P2 Q2
                                 ...

     PN QN
      R1 S 1
      R2 S 2
                                 ...

     RM S M


出力

 標準出力に,JOI 君の庭を構成するマスの個数の最小値を1 行で出力せよ.


制約

    • N ≧1.

    • M ≧1.

    • N + M ≦500 000.

    • 1 ≦D ≦5 000.
    • 0 ≦Pi < D (1 ≦i ≦N).
    • 0 ≦Qi < D (1 ≦i ≦N).
    • 0 ≦Rj < D (1 ≦j ≦M).
    • 0 ≦S j < D (1 ≦j ≦M).
    • 入力される値はすべて整数である.





                          庭園– 2 / 4

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)

                                                                  JOI Open Contest

                                                                            August 5, 2023


                                                                              garden



小課題

    1. (15 点) M ≦8.

    2. (6 点) D ≦10,N + M ≦5000.

    3. (8 点) D ≦50,N + M ≦5000.

    4. (16 点) D ≦100,N + M ≦5000.

    5. (30 点) N + M ≦5000.

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


入出力例

  入力例1              出力例1

   2 1 5                          8

   1 4

   2 2

   0 0

  JOI 王国の領地のうち,0 ≦x < 10, 0 ≦y < 10 を満たす整数x, y を用いて(x, y) と表されるマスについて

図示したものが次の図である.





                          庭園– 3 / 4

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)

                                                                  JOI Open Contest

                                                                            August 5, 2023


                                                                              garden


 円と菱形はそれぞれタイプA,B のオブジェを表し,中に書かれた数字はオブジェの種類を表す.

a = 1, b = 2, c = 2, d = 5 と選ぶと,JOI 君の庭は図で黒く塗られた部分になる.このとき,3 種類あるオブ

ジェのすべてが庭に置かれている.この庭を構成するマスの個数は8 であり,これより少ないマスの個数で

条件を満たす庭は存在しない.よって8 を出力する.

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


  入力例2              出力例2

   3 4 100                        2840

   20 26

   81 56

   20 3

   58 71

   74 82

   95 61

   95 61

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


  入力例3              出力例3

   5 7 5000                       10543092

   1046 365

   4122 1166

   4009 2896

   1815 4065

   4372 1651

   2382 123

   1475 836

   3313 4005

   2579 568

   4300 4867

   1050 3214

   3589 4653

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





                          庭園– 4 / 4