← 返回题目列表

AtCoder · joisc2019_c

C. 馕

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

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

ナン (Naan) - 原题 PDF 第 1 页
原题PDF第1页
ナン (Naan) - 原题 PDF 第 2 页
原题PDF第2页
ナン (Naan) - 原题 PDF 第 3 页
原题PDF第3页
ナン (Naan) - 原题 PDF 第 4 页
原题PDF第4页
可复制的 PDF 提取文本
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)

                                                         Spring Training Camp/Qualifying Trial

                                            March 19–25, 2019 (Komaba/Yoyogi, Tokyo)


                                                                           Contest Day 1 – Naan

                    ナン(Naan)



  JOI カレー店はとても長いナンを出すことで有名である.この店ではナンにL 種類の味付けを行ってお

り,味はそれぞれ1 以上L 以下の整数で番号付けされている.この店の目玉商品であるJOI スペシャルナ

ンは長さがL cm であり,左からj −1 cm からj cm の部分は味j で味付けされている(1 ≦j ≦L).

 あなたはお腹が空いたので,昼ごはんを食べにN 人でJOI カレー店に来た.みんなで1 つのJOI スペ

シャルナンを食べるつもりである.人によって味の好みは異なる.i 番目(1 ≦i ≦N) の人は味j (1 ≦j ≦L)
で味付けされたナンを食べると1 cm あたりVi,j の幸福度を得る.
 あなたはJOI スペシャルナンをN 個のピースに切り分けて,みんなに分配することにした.具体的には,

以下の手順でナンを分配する.

    1. N −1 個の有理数0 < X1 < X2 < · · · < XN−1 < L を決める.
    2. N 個の整数P1, P2, . . . , PN を決める.これは1 以上N 以下の整数の並び替えでなければならない.
    3. 各整数k (1 ≦k ≦N −1) に対して,ナンの左からXk cm の場所をそれぞれ切る.これにより,ナン
   はN 個のピースに切り分けられる.
    4. 各整数k (1 ≦k ≦N) に対して,ナンの左からXk−1 cm のところからXk cm のところまでに該当する
   ピースをPk 番目の人に与える.ここで,X0 = 0, XN = L とする.

 人によって味の好みが異なるので,なるべく公平になるように分配したい.どの人も,JOI スペシャルナ
ンを1 人ですべて食べたときの幸福度の1 以上の幸福度が得られる分配を公平な分配と呼ぶ.あなたの目
                          N
標は公平な分配を1 つ見つけることである.

 人の味の好みが与えられたとき,公平な分配が可能かどうかを判定し,もし可能ならば公平な分配を1 つ

求めるプログラムを作成せよ.


入力


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


    N L

       V1,1 V1,2 · · · V1,L
                                 ...

       VN,1 VN,2 · · · VN,L





                          ナン– 1 / 4

The 18th Japanese Olympiad in Informatics (JOI 2018/2019)

                                                         Spring Training Camp/Qualifying Trial

                                            March 19–25, 2019 (Komaba/Yoyogi, Tokyo)


                                                                           Contest Day 1 – Naan



出力

 公平な分配が不可能ならば,標準出力に−1 を出力せよ.公平な分配が可能ならば,標準出力にその分配
を表すN −1 個の有理数X1, . . . , XN−1 とN 個の整数P1, . . . , PN を以下の形式で出力せよ.

      A1 B1
      A2 B2
                                 ...

      AN−1 BN−1
      P1 P2 · · · PN

                       Ak
 ここで,Ak, Bk はXk =  を満たす整数の組である(1 ≦k ≦N −1).これらの整数は「出力の制約」の条
                        Bk
件を満たすこと.


入力の制約

    • 2 ≦N ≦2 000.

    • 1 ≦L ≦2 000.
    • 1 ≦Vi, j ≦100 000 (1 ≦i ≦N, 1 ≦j ≦L).


出力の制約


 公平な分配が可能な場合,出力は以下の制約を満たさなければならない.

    • 1 ≦Bk ≦1 000 000 000 (1 ≦k ≦N −1).
          A1   A2        AN−1
    • 0 <   <   < · · · <    < L.
          B1   B2        BN−1
    • P1, . . . , PN は1 以上N 以下の整数の並び替えである.
    • 出力された分配において,i 番目の人が得る幸福度がVi,1 + Vi,2 + · · · + Vi,L 以上である(1 ≦i ≦N).
                                           N

なお,Ak とBk は互いに素でなくてもよい(1 ≦k ≦N −1).
 この問題の制約の下,公平な分配が存在するならば,1 ≦Bk ≦1 000 000 000 (1 ≦k ≦N −1) を満たす正

しい出力が存在することが証明できる.





                          ナン– 2 / 4

The 18th Japanese Olympiad in Informatics (JOI 2018/2019)

                                                         Spring Training Camp/Qualifying Trial

                                            March 19–25, 2019 (Komaba/Yoyogi, Tokyo)


                                                                           Contest Day 1 – Naan



小課題

    1. (5 点) N = 2.
    2. (24 点) N ≦6,Vi,j ≦10 (1 ≦i ≦N, 1 ≦j ≦L).
    3. (71 点) 追加の制約はない.


入出力例

  入力例1              出力例1

   2 5                            14 5

   2 7 1 8 2                      2 1

   3 1 4 1 5

 この入力例では,1 番目の人がナンを1 人で全部食べたときに得る幸福度が2 + 7 + 1 + 8 + 2 = 20 で,2

番目の人がナンを1 人で全部食べたときに得る幸福度が3 + 1 + 4 + 1 + 5 = 14 である.よって,1 番目の人
が20 = 10 以上,2 番目の人が14 = 7 以上の幸福度が得られる分配が公平な分配になる.
   2                       2
 左から14 cm のところでナンを分け,1 番目の人に左から2 つめのピースを,2 番目の人に左から1
         5
                                                1          51
つめのピースを与えるようにすると,1 番目の人は1 ×  + 8 + 2 =  の幸福度を得て,2 番目の人は
                                                5           5
          4   36
3 + 1 + 4 ×  =  の幸福度を得るので,公平な分配になる.
          5   5

  入力例2              出力例2

   7 1                            1 7

   1                              2 7

   2                              3 7

   3                              4 7

   4                              5 7

   5                              6 7

   6                              3 1 4 2 7 6 5

   7

 この入力例では,ナンの味が1 種類しかないので,ナンを7 等分する以外に公平な分配はない.どのピー

スも味が同じなので,誰がどれを食べても公平な分配になる.





                          ナン– 3 / 4

The 18th Japanese Olympiad in Informatics (JOI 2018/2019)

                                                       Spring Training Camp/Qualifying Trial

                                           March 19–25, 2019 (Komaba/Yoyogi, Tokyo)


                                                                         Contest Day 1 – Naan


 入力例3              出力例3

 5 3                            15 28

 2 3 1                          35 28

 1 1 1                          50 28

 2 2 1                          70 28

 1 2 2                          3 1 5 2 4

 1 2 1

出力においてAk とBk が互いに素である必要はない(1 ≦k ≦N −1).





                        ナン– 4 / 4