bikesvscars
EGOI Day 1 Tasks
Japanese (JPN)

自転車 vs 車 (Bikes vs Cars)
問題名自転車 vs 車 (Bikes vs Cars)

実行時間制限

5 sec

メモリ制限

1 GB

Lund では，自転車に乗ることはとても一般的な移動手段である．しかし，車と自転車の両方が細い道路の上を通るのはときに難しい．状況を改善するために，知事は地域の道路網を完全に設計し直したがっている．
Lund には 0 から N − 1 までの番号が付けられた N 個の主要地点があり，人々はその間を頻繁に行き来する．人々は，パス，すなわち一方の地点から他方の地点へと続く道路の列を辿ることで 2 つの地点の間を行き来する．ある乗り物（車あるいは自転車）は，あるパスにおいてすべての関係するレーンの幅がその乗り物の幅以上である場合，そのパス上を行き来することができる．新しく建設された各道路はこれらの主要地点のうちの 2 つを結び，合計で W の道幅がある．この道幅は自転車用レーンと車用レーンの間で任意に分割することができる．Lund では，あるエンジニア達が幅 0 の自転車および車を発明したばかりである（これらは幅 0 のレーン上を行き来することができる）．
エンジニア達は都市内の車および自動車の幅を測定した．主要地点の組のそれぞれについて，彼らはそれらの地点間を行き来できなければならない車の最大幅と自転車の最大幅を知っているが，一方で知事はそれより幅の大きい車や自転車がその地点間を行き来できなくするように求めている．
形式的には，それぞれの組 i, j (0 ≤ i < j ≤ N − 1) に対して 2 つの整数値 Ci,j ，Bi,j が与えられる．あなたのタスクは N 個の地点を結ぶ道を構築することである．道路はみな W の道幅があるが，それぞれの道路 s おける自転車用レーンの幅 bs はあなたが決めることができ，これはその道路の車用レーンの幅を W − bs に定める．道路網は以下の条件を満たさなければならない：
どの 2 つの地点間も行き来可能でなければならない．この条件は幅 0 の自転車ないしは車を必要とするかもしれないことに留意すること．
それぞれの地点の組 i , j (i < j ) について，車用レーンの幅が Ci,j 以上である道路だけを用いて i と jの間を行き来することが可能である．また， Ci,j はこの条件を満たす最大の数である．つまり，地点 i と jを結ぶすべてのパスにおいて，車用レーンの幅が Ci,j 以下であるような道路が 1 つ以上存在する．
それぞれの地点の組 i , j (i < j ) について，自転車用レーンの幅が Bi,j 以上である道路だけを用いて iと j の間を行き来することが可能である．また， Bi,j はこの条件を満たす最大の数である．
Lund の知事がそのような道路網を設計するのを手伝ってくれますか？資金は限られているので，あなたは最大でも 2023 本の道路しか建設できない．あなたは同じ主要地点の組の間に複数の道路を建設してもよいが，ある地点とそれ自身を繋ぐことはできない．すべての道路は双方向に通行可能である．

bikesvscars (1 of 5)

入力
入力の 1 行目には 2 つの整数 N ，W が書かれている．これらは Lund の主要地点の数およびあなたが建設できる道路の道幅である．
続く N − 1 行には Ci,j の情報が書かれている．これらの行のうち j 行目には i < j を満たす各 Ci,j の情報が書かれている．ゆえに 1 行目には C0,1 のみが書かれ，2 行目には C0,2 と C1,2 が書かれ，3 行目には C0,3 とC1,3 と C2,3 が書かれ，以下同様である．
続く N − 1 行には Bi,j の情報が Ci,j と同じ形式で書かれている．

出力
そのような道路網を構築することが不可能ならば，文字列 "NO" を 1 行に出力せよ．
そうでないならば，あなたの道路網に含まれる道路の数を表す整数 M を 1 行に出力せよ．
続く M 行のそれぞれにおいて，3 つの整数 u, v, b を出力せよ．これは u と v を結び自動車用レーンの幅が bである道路を指す（そして車用レーンの幅は W − b である）．
あ な た は 最 大 で 2023 本 の 道 路 を 使 う こ と が で き る ． あ な た が 出 力 す る 道 路 は 0 ≤ b ≤ W ,0 ≤ u, v ≤ N − 1 および u ≠ v を満たさなければならない．同じ主要地点の組を結ぶ，（自転車用レーンの幅が相異なるかもしれない）複数の道路を使っても構わない．
複数の解がある場合は，そのどれを出力しても構わない．

制約および評価方法
2 ≤ N ≤ 500.
1 ≤ W ≤ 106 .
0 ≤ Ci,j , Bi,j ≤ W (0 ≤ i < j ≤ N − 1).
あなたの解答はいくつかの小課題においてテストされ，それぞれについて得点が定められている．それぞれの小課題はいくつかのテストケースを含む．ある小課題の得点を得るためには，その小課題に含まれるすべてのテストケースに対して正答する必要がある．

bikesvscars (2 of 5)

小課題

得点

制約

1

10

すべての Ci,j は等しく, すべての Bi,j は等しく, N ≤ 40．

2

5

すべての Ci,j は等しく, すべての Bi,j は等しい．

317N ≤ 40．

418

W = 1．

5

19

すべての Bi,j は等しい．

631

追加の制約はない．

例
最初の例では，道幅は 1 であり，幅が 1 以上である車用レーンと自転車用レーンが地点 0 と 1 の間に必要である．出力例の解では幅 1 の自転車用レーンを持った道路と幅 1 の車用レーンを持った道路の 2 本を 2 地点の間に設けている．

2 つ目の例では，道幅は再び 1 であり，幅 1 の自転車用レーンを持つパスが全ての主要地点の組の間に存在しなければならず，すべての道路について車用レーンの幅が 1 であるようなパスが，地点 1 と 2 の間および地点 2と 3 の間に存在しなければならない．これは，C1,3 = 0 であるので 1 と 3 を結び車用レーンの幅が 1 であるようなパスがあってはならないという事実に反する．なぜなら，前述の 2 つのパスを連結することでそのようなパスが構成できるからである．したがって，そのような道路網を構築することはできない．

3 つ目の例では，下の道路網がすべての条件を満たす．例えば，車用レーンの幅の最小値が 1 = C0,5 であるよ
うなパスが地点 0 と 5 の間に（例えば 0 → 2 → 4 → 5 という経路を辿ることによって）存在し，自転車用レーンの幅の最小値が 3 = B0,5 であるようなパスが（例えば 0 → 3 → 4 → 5 という経路を辿ることによって）存在する．同時に，どの繋がりについても，最小の幅がより大きいようなパスが存在しないことを確認できる．3 つ目の例には他にも多くの解が存在することに留意せよ．

bikesvscars (3 of 5)bikesvscars (4 of 5)

入力

出力2 1120 1 0

10 1 1

4 1

NO00 1
0 0 1
11 1
1 1 1

6 65

80 1 14 4
1 1 10 2 3
1 2 2

1 1 1 30 3 6

1 1 1 5 3
22 4 53 4 33 2

3 5 1

6 2 3
3 2 5 34 5 4

3 2 4 3 4

bikesvscars (5 of 5)