← 返回题目列表

AtCoder · joisc2021_b

B. IOI热的蔓延(IOI热)

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

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

IOI 熱の感染拡大 (IOI Fever) - 原题 PDF 第 1 页
原题PDF第1页
IOI 熱の感染拡大 (IOI Fever) - 原题 PDF 第 2 页
原题PDF第2页
IOI 熱の感染拡大 (IOI Fever) - 原题 PDF 第 3 页
原题PDF第3页
IOI 熱の感染拡大 (IOI Fever) - 原题 PDF 第 4 页
原题PDF第4页
IOI 熱の感染拡大 (IOI Fever) - 原题 PDF 第 5 页
原题PDF第5页
IOI 熱の感染拡大 (IOI Fever) - 原题 PDF 第 6 页
原题PDF第6页
可复制的 PDF 提取文本
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                          Spring Training Camp/Qualifying Trial

                                                   March 20–23, 2021 (Komaba, Tokyo)


                                                                        Contest Day 1 – IOI Fever

                  IOI 熱の感染拡大(IOI Fever)



   JOI 国はxy 座標平面として表される.JOI 国にはN 軒の家があり,家には1 からN までの番号が付けら
 れている.家i (1 ≦i ≦N) は座標(Xi, Yi) にあり,同じ座標に複数の家は存在しない.また,各家には1 人
 の国民が住んでおり,家i に住んでいる国民を国民i と表す.今,JOI 国では大型連休が始まろうとしてい

 る.時刻0 になるとすべての国民は同時に家を出発し,旅行を始める.最初に,各国民は「東」「西」「南」

「北」のうちいずれかの方向を選択し,以下の通りに動く.

     • 国民i が「東」を選択した場合:x 軸の正の方向に速さ1 で動く.つまり,時刻t (t ≧0) における国
    民i の座標は(Xi + t, Yi) となる.
     • 国民i が「西」を選択した場合:x 軸の負の方向に速さ1 で動く.つまり,時刻t (t ≧0) における国
    民i の座標は(Xi −t, Yi) となる.
     • 国民i が「南」を選択した場合:y 軸の負の方向に速さ1 で動く.つまり,時刻t (t ≧0) における国
    民i の座標は(Xi, Yi −t) となる.
     • 国民i が「北」を選択した場合:y 軸の正の方向に速さ1 で動く.つまり,時刻t (t ≧0) における国
    民i の座標は(Xi, Yi + t) となる.

  残念なことに,時刻0 に国民1 が新型の感染症であるIOI 熱に感染してしまった.時刻0 において,国

 民1 以外には感染者はいない.IOI 熱は国民の間で次のように伝染する.

    ある時刻において国民a (1 ≦a ≦N) と国民b (1 ≦b ≦N) が同じ座標に存在し,その時点で国民a

    が感染者で国民b が非感染者であった場合,国民b が新たに感染する.

 これ以外の方法で新たな感染者が発生することはない.また,IOI 熱は不治の病であるため,感染者は二度

と非感染者になることはない.

   JOI 国の大臣であるあなたは,国民が最悪な方向を選択した場合,何人の国民がIOI 熱に感染するかを見

積もらなければならない.

  家の軒数と各家の座標が与えられたとき,時刻10100 における感染者数としてあり得る最大値を求めるプ

ログラムを作成せよ.





                                      IOI 熱の感染拡大– 1 / 6

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2021 (Komaba, Tokyo)


                                                                       Contest Day 1 – IOI Fever



入力


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


    N

      X1 Y1
                                 ...

     XN YN


出力

 標準出力に,時刻10100 における感染者数としてあり得る最大値を1 行で出力せよ.


制約

    • 1 ≦N ≦100 000.
    • 0 ≦Xi ≦500 000 000 (1 ≦i ≦N).
    • 0 ≦Yi ≦500 000 000 (1 ≦i ≦N).
    • (Xi, Yi) , (Xj, Yj) (1 ≦i <  j ≦N).


小課題

    1. (5 点) N ≦7,Xi , Xj (1 ≦i <  j ≦N),Yi , Y j (1 ≦i <  j ≦N).
    2. (8 点) N ≦15,Xi , Xj (1 ≦i <  j ≦N),Yi , Yj (1 ≦i <  j ≦N).
    3. (6 点) N ≦100,Xi , Xj (1 ≦i <  j ≦N),Yi , Yj (1 ≦i <  j ≦N),X1 = 0,Y1 = 0.
    4. (6 点) N ≦100,Xi , Xj (1 ≦i <  j ≦N),Yi , Yj (1 ≦i <  j ≦N).
    5. (12 点) N ≦3 000.
    6. (32 点) Xi , X j (1 ≦i <  j ≦N),Yi , Y j (1 ≦i <  j ≦N).
    7. (31 点) 追加の制約はない.





                                     IOI 熱の感染拡大– 2 / 6

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2021 (Komaba, Tokyo)


                                                                       Contest Day 1 – IOI Fever



入出力例

  入力例1              出力例1

   2                              1

   0 0

   4 3

 この入力例における家の位置関係は下図の通りとなる.


                           y

                        3                                              2




                        2




                        1


               1
                                      1            2            3            4      x



 例えば,国民1 が「東」,国民2 が「南」の方向を選択したとする.

 このとき,国民2 は国民1 と同じ座標に存在することはないので,国民2 は感染しない.したがって,時
刻10100 での感染者は国民1 のみであり,感染者数は1 人である.

 国民1,国民2 がどのような方向を選択したとしても,感染者数が2 人以上とはならない.したがって,

求める感染者数の最大値は1 人であるため,1 を出力する.


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





                                     IOI 熱の感染拡大– 3 / 6

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2021 (Komaba, Tokyo)


                                                                       Contest Day 1 – IOI Fever


  入力例2              出力例2

   3                              3

   1 2

   2 1

   4 3

 この入力例における家の位置関係は下図の通りとなる.


                           y

                        3                                              3




                        2                       1




                        1                               2





                                      1            2            3            4      x



 例えば,国民1 が「東」,国民2 が「北」,国民3 が「西」の方向を選択したとする.このとき,以下のよ

うに感染が拡大していく.

    • 時刻0 において,国民1 のみがIOI 熱に感染している.

    • 時刻1 において,国民1, 2, 3 の座標は順に(2, 2), (2, 2), (3, 3) となる.国民1 と2 が同じ座標に存在

   し,国民1 はその時点で感染者であるため,非感染者である国民2 が新たに感染する.

    • 時刻2 において,国民1, 2, 3 の座標は順に(3, 2), (2, 3), (2, 3) となる.国民2 と3 が同じ座標に存在

   し,国民2 はその時点で感染者であるため,非感染者である国民3 が新たに感染する.

 このとき,最終的な感染者数は3 人となる.これが最大値であるため,3 を出力する.


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





                                     IOI 熱の感染拡大– 4 / 6

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                       Spring Training Camp/Qualifying Trial

                                                March 20–23, 2021 (Komaba, Tokyo)


                                                                     Contest Day 1 – IOI Fever


 入力例3              出力例3

 2                              2

 20 20

 20 21

国民1 が「北」,国民2 が「南」の方向を選択した場合,以下のように感染が拡大していく.

  • 時刻0 において,国民1 のみがIOI 熱に感染している.

  • 時刻0.5 において,国民1, 2 両方が座標(20, 20.5) に存在する.国民1 はその時点で感染者であるた

  め,非感染者である国民2 が新たに感染する.

このとき,最終的な感染者数は2 人となる.これが最大値であるため,2 を出力する.

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



 入力例4              出力例4

 15                             9

 5 6

 2 9

 12 0

 4 11

 3 12

 6 5

 0 8

 9 10

 11 13

 8 7

 13 2

 1 1

 7 14

 10 4

 14 3

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





                                   IOI 熱の感染拡大– 5 / 6

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                       Spring Training Camp/Qualifying Trial

                                                March 20–23, 2021 (Komaba, Tokyo)


                                                                     Contest Day 1 – IOI Fever


 入力例5              出力例5

 30                             11

 275810186 246609547

 122805872 99671769

 243507947 220373844

 281305347 252104708

 237805644 214671541

 172469077 149334974

 222589229 229887956

 160653451 208404690

 241378966 211098219

 144302355 224755786

 186392385 163258282

 199129390 169928751

 294937491 265736852

 196096122 172962019

 314342944 285142305

 202720470 166337671

 157037485 133903382

 263858979 240724876

 210720220 181519581

 296402036 267201397

 186021287 183036854

 195081930 173976211

 328293029 299092390

 261195361 238061258

 323595085 294394446

 299933764 270733125

 240976723 128081418

 188501753 165367650

 277832422 248631783

 119896220 96762117

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





                                   IOI 熱の感染拡大– 6 / 6