← 返回题目列表

AtCoder · joigsc2022_b

B. JOIG 巡演

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

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

JOIG ツアー (JOIG Tour) - 原题 PDF 第 1 页
原题PDF第1页
JOIG ツアー (JOIG Tour) - 原题 PDF 第 2 页
原题PDF第2页
JOIG ツアー (JOIG Tour) - 原题 PDF 第 3 页
原题PDF第3页
JOIG ツアー (JOIG Tour) - 原题 PDF 第 4 页
原题PDF第4页
JOIG ツアー (JOIG Tour) - 原题 PDF 第 5 页
原题PDF第5页
JOIG ツアー (JOIG Tour) - 原题 PDF 第 6 页
原题PDF第6页
JOIG ツアー (JOIG Tour) - 原题 PDF 第 7 页
原题PDF第7页
JOIG ツアー (JOIG Tour) - 原题 PDF 第 8 页
原题PDF第8页
可复制的 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 – JOIG Tour

                JOIG ツアー(JOIG Tour)



 あなたはJust Odd Ink 街道を知っているだろうか?この街道はEGOI 国を東西に横断する長さ10100 の街

道であり,「ただ奇妙なインク(just odd ink)」によって描かれたたくさんのアートで有名である.ここでは

略してJOI 街道と呼ぶ.

 さて,JOI 街道には大小様々なアートが描かれているが,そのうちいくつかは文字が描かれているように

見える.

  JOI 街道のツアーガイドである理恵さんは,JOIG 春合宿の参加者を案内することになった.JOIG 春合宿

の参加者を喜ばせたい理恵さんは,JOI 街道に描かれているアートのうち,‘J’, ‘O’, ‘I’, ‘G’ と読めるアート

をこの順に訪れるツアーの計画を考えている.訪れる候補となるアートはN 個あり,i 番目(1 ≦i ≦N) の
アートはJOI 街道の西端から距離Ai の地点にあり,このアートはCi と読める.
 理恵さんはQ 個の計画を考えている.j 番目(1 ≦j ≦Q) の計画におけるツアーでは,以下の順に移動を

行う.

    1. JOI 街道の西端から距離S j の地点からツアーを開始する.
    2. ‘J’ と読めるアートがある地点を1 つ選び,その地点に移動する.

    3. ‘O’ と読めるアートがある地点を1 つ選び,その地点に移動する.

    4. ‘I’ と読めるアートがある地点を1 つ選び,その地点に移動する.

    5. ‘G’ と読めるアートがある地点を1 つ選び,その地点に移動する.
    6. JOI 街道の西端から距離T j の地点に移動し,ツアーを終了する.

ただし,ツアーの経路はJOI 街道を外れないものとする.

 理恵さんはこの条件のもと,それぞれの計画についてなるべくツアーの総移動距離を短くしたい.

  JOI 街道のアートの情報と理恵さんの計画の情報が与えられたとき,それぞれの計画について,ツアーの

総移動距離の最小値を求めるプログラムを作成せよ.





                                  JOIG ツアー– 1 / 8

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                          Contest 1 – JOIG Tour



入力


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


    N

      A1 C1
      A2 C2
                                 ...

     AN CN

    Q

      S 1 T1
      S 2 T2
                                 ...

      S Q TQ


出力

 標準出力にQ 行で出力せよ.j 行目(1 ≦j ≦Q) には,理恵さんのj 番目の計画におけるツアーの総移動

距離の最小値を出力せよ.


制約

    • 4 ≦N ≦100 000.
    • 1 ≦Ai ≦1 000 000 000 000 000 (= 1015) (1 ≦i ≦N).
    • Ai < Ai+1 (1 ≦i ≦N −1).
    • Ci (1 ≦i ≦N) は‘J’,‘O’,‘I’,‘G’ のいずれかである.
    • Ci が‘J’ であるようなi (1 ≦i ≦N) は1 つ以上存在する.
    • Ci が‘O’ であるようなi (1 ≦i ≦N) は1 つ以上存在する.
    • Ci が‘I’ であるようなi (1 ≦i ≦N) は1 つ以上存在する.
    • Ci が‘G’ であるようなi (1 ≦i ≦N) は1 つ以上存在する.
    • 1 ≦Q ≦100 000.
    • 1 ≦S j ≦1 000 000 000 000 000 (= 1015) (1 ≦j ≦Q).
    • 1 ≦T j ≦1 000 000 000 000 000 (= 1015) (1 ≦j ≦Q).
    • (S j, T j) , (S k, Tk) (1 ≦j < k ≦Q).



                                  JOIG ツアー– 2 / 8

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                          Contest 1 – JOIG Tour


    • N, Q は整数である.
    • Ai は整数である(1 ≦i ≦N).
    • S j, T j は整数である(1 ≦j ≦Q).


小課題

    1. (4 点) N ≦80,Q ≦10.

    2. (10 点) N ≦500,Q ≦10.

    3. (6 点) N ≦3 000,Q ≦100.

    4. (25 点) N ≦5 000,Q ≦1 000.
    5. (12 点) Ci が‘O’ であるようなi (1 ≦i ≦N),C j が‘I’ であるようなj (1 ≦j ≦N),Ck が‘G’ である
   ようなk (1 ≦k ≦N) はそれぞれただ1 つ存在する.
    6. (8 点) Ci が‘O’ であるようなi (1 ≦i ≦N) ,C j が‘I’ であるようなj (1 ≦j ≦N) はそれぞれただ1

   つ存在する.

    7. (20 点) Ci が‘O’ であるようなi (1 ≦i ≦N) はただ1 つ存在する.
    8. (15 点) 追加の制約はない.


入出力例

  入力例1              出力例1

   7                              7

   1 J                            12

   2 O

   3 G

   4 I

   5 O

   8 G

   10 J

   2

   3 2

   7 5





                                  JOIG ツアー– 3 / 8

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                          Contest 1 – JOIG Tour


  1 番目の計画は,JOI 街道の西端から距離3 の地点からツアーを開始し,西端から距離2 の地点でツアー

を終了するというものである.例えば,以下のように移動することで,ツアーの総移動距離を7 とすること

ができる.

    1. JOI 街道の西端から距離3 の地点からツアーを開始する.

    2. 西に距離2 だけ移動し,JOI 街道の西端から距離1 の地点にある‘J’ と読めるアートを訪れる.

    3. 東に距離1 だけ移動し,JOI 街道の西端から距離2 の地点にある‘O’ と読めるアートを訪れる.

    4. 東に距離2 だけ移動し,JOI 街道の西端から距離4 の地点にある‘I’ と読めるアートを訪れる.

    5. 西に距離1 だけ移動し,JOI 街道の西端から距離3 の地点にある‘G’ と読めるアートを訪れる.

    6. 西に距離1 だけ移動し,JOI 街道の西端から距離2 の地点でツアーを終了する.

ツアーの総移動距離を7 未満にすることはできないため,7 を1 行目に出力する.

  2 番目の計画は,JOI 街道の西端から距離7 の地点からツアーを開始し,西端から距離5 の地点でツアー

を終了するというものである.例えば,以下のように移動することで,ツアーの総移動距離を12 とするこ

とができる.

    1. JOI 街道の西端から距離7 の地点からツアーを開始する.

    2. 東に距離3 だけ移動し,JOI 街道の西端から距離10 の地点にある‘J’ と読めるアートを訪れる.

    3. 西に距離5 だけ移動し,JOI 街道の西端から距離5 の地点にある‘O’ と読めるアートを訪れる.

    4. 西に距離1 だけ移動し,JOI 街道の西端から距離4 の地点にある‘I’ と読めるアートを訪れる.

    5. 西に距離1 だけ移動し,JOI 街道の西端から距離3 の地点にある‘G’ と読めるアートを訪れる.

    6. 東に距離2 だけ移動し,JOI 街道の西端から距離5 の地点でツアーを終了する.

ツアーの総移動距離を12 未満にすることはできないため,12 を2 行目に出力する.

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





                                  JOIG ツアー– 4 / 8

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)

                                                       Spring Training Camp/Qualifying Trial

                                                March 20–23, 2022 (Komaba, Tokyo)


                                                                        Contest 1 – JOIG Tour


 入力例2              出力例2

 10                             13

 5 J                            19

 7 O                            20

 10 J                           21

 11 G

 12 J

 13 I

 17 J

 18 J

 19 J

 20 J

 4

 4 9

 15 14

 6 20

 7 20

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





                                JOIG ツアー– 5 / 8

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)

                                                       Spring Training Camp/Qualifying Trial

                                                March 20–23, 2022 (Komaba, Tokyo)


                                                                        Contest 1 – JOIG Tour


 入力例3              出力例3

 10                             25

 1 G                            27

 2 J                            28

 3 G                            17

 4 O                            26

 7 G                            39

 9 J                            30

 10 G

 14 I

 17 G

 19 G

 7

 11 6

 6 3

 17 19

 1 18

 17 17

 20 1

 20 10

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





                                JOIG ツアー– 6 / 8

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)

                                                       Spring Training Camp/Qualifying Trial

                                                March 20–23, 2022 (Komaba, Tokyo)


                                                                        Contest 1 – JOIG Tour


 入力例4              出力例4

 10                             12

 3 J                            17

 5 G                            15

 6 I                            15

 7 I                            19

 8 J                            12

 9 I

 10 O

 14 G

 16 I

 19 J

 6

 4 4

 20 3

 18 5

 15 4

 20 11

 10 8

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





                                JOIG ツアー– 7 / 8

The 2nd Japanese Olympiad in Informatics for Girls (JOIG 2021/2022)

                                                       Spring Training Camp/Qualifying Trial

                                                March 20–23, 2022 (Komaba, Tokyo)


                                                                        Contest 1 – JOIG Tour


 入力例5                  出力例5

 12                                   583302366935305

 179948747891578 I                    805077987955000

 263779425244614 I                    591304613119987

 320153642407146 G                    757352272699625

 383698990675423 J                    478217003098189

 478483318441339 J                    869691499240121

 505589213620811 G                    805495866954969

 507468309040564 O                    1085532869547991

 530441288489671 J                    928541333618299

 730036011088087 O                    1205618838253516

 896127332008998 I

 899298512463927 O

 915990785839829 J

 10

 744829561026263 366031656398270

 700496830781726 684771674298690

 314138534887378 222241904398827

 695615197615084 632164325876673

 418419052313523 409258287819812

 932490604948180 62799105708059

 738126150487131 45378717857226

 320047965627255 918203067583346

 859632377126681 967370566306944

 115848334010451 834089404672067

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





                                JOIG ツアー– 8 / 8