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




可复制的 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