AT_ahc037_a [AHC037A] Soda

[problemUrl]: https://atcoder.jp/contests/ahc037/tasks/ahc037_a 炭酸飲料の**甘さ**と**炭酸の強さ**は、それぞれ非負整数で表されます。甘さ $ x $、炭酸の強さ $ y $ の炭酸飲料を $ (x,\ y) $ と表記します。 あなたは最初、炭酸飲料 $ (0,\ 0) $ だけを持っています。以下、すでに作られた炭酸飲料の集合を $ S $ と書きます。最初は $ S\ =\ \{(0,\ 0)\} $ です。 あなたは以下の操作を繰り返し行うことで複数の炭酸飲料を作ることができます。 - すでに持っている炭酸飲料 $ (x,\ y)\ \in\ S $ を一つ選ぶ - $ x'\ \ge\ x $ かつ $ y'\ \ge\ y $ を満たす整数 $ x',\ y' $ を選ぶ - $ (x,\ y) $ を二つの容器に分ける。片方はそのまま取っておき、もう一方にシロップと炭酸を加えることで炭酸飲料 $ (x',\ y') $ を作る。$ S $ に $ (x',\ y') $ が追加される。 - このとき $ (x,\ y) $ が $ S $ から削除**されない**ことに注意してください - コストが $ (x'\ -\ x)\ +\ (y'\ -\ y) $ かかる 入力として $ N $ 種類の炭酸飲料 $ (A_1,\ B_1),\ \dots,\ (A_N,\ B_N) $ が指定されます。操作を $ 5N $ 回まで行えるとき、指定された炭酸飲料をすべて作るような操作列（つまり、操作をすべて終えたときにどの $ i\ \in\ \{1,\ 2,\ \dots,\ N\} $ に対しても $ (A_i,\ B_i)\ \in\ S $ が成り立つ操作列）のうち、コストの総和がなるべく小さいものを見つけてください。途中で入力に含まれない炭酸飲料が作られても構いません。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_N $ $ B_N $ 入力はすべて整数であり、以下の制約を満たす。 - $ N\ =\ 1000 $ - $ 0\ \le\ A_i\

操作の回数を $ M $ とする。$ m $ 回目の操作で $ (x_m,\ y_m) $ から $ (x'_m,\ y'_m) $ を作るとして、以下のフォーマットで標準出力に出力せよ。 > $ M $ $ x_1 $ $ y_1 $ $ x'_1 $ $ y'_1 $ $ \vdots $ $ x_M $ $ y_M $ $ x'_M $ $ y'_M $ 出力はすべて整数で、以下の条件を満たさなければならない。 - $ 0\ \le\ M\ \le\ 5N $ - $ 0\ \le\ x_m\ \le\ x'_m\

### ストーリー あなたはある飲料工場で働いています。この工場では、ベースとなる飲料水が大量に用意されており、それにシロップと炭酸を加えることで製品である炭酸飲料を作ります。加えるシロップと炭酸の量を変えることで複数の炭酸飲料を作ることができます。さらに、すでに作られた炭酸飲料にシロップや炭酸を追加して別の炭酸飲料を作ることも可能です。 作りたい炭酸飲料の甘さと炭酸の強さの組合わせが複数与えられたとき、なるべく効率的にそれらを作る手順を見つけてください。 ### 得点 コストの総和を $ C $ とし、$ L\ =\ \max\{A_1,\ B_1,\ A_2,\ B_2,\ \dots,\ A_N,\ B_N\} $ とする。このとき得点は $ \mathrm{round}\left(10^6\ \times\ \frac{NL}{1\ +\ C}\right) $ で与えられる。 テストケースは全部で 150 個あり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定が WA や TLE となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 $ N\ =\ 1000 $ とする。 $ A_1,\ \dots,\ A_N $ を以下のように生成する。 - $ a_1\ =\ 0 $ とし、$ a_2,\ \dots,\ a_N $ を $ 1 $ 以上 $ 10^9 $ 未満の範囲から重複しないよう一様ランダムに選ぶ - $ a_1,\ \dots,\ a_N $ をランダムに並べ替えたものを $ A_1,\ \dots,\ A_N $ とする $ B_1,\ \dots,\ B_N $ も同様の方法で生成する。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc037/WneGTzJP.html?lang=ja): ローカル版より高性能でアニメーション表示が可能です。 - [ローカル版](https://img.atcoder.jp/ahc037/WneGTzJP.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc037/WneGTzJP_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。 ### Sample Explanation 1 これは説明のための例であり、入力の制約は満たしていません。 作りたい炭酸飲料は $ (0,\ 6),\ (2,\ 5),\ (3,\ 2),\ (4,\ 0) $ です。問題文と同様に、すでに作られた炭酸飲料の集合を $ S $ で表します。 - 最初の操作では $ (0,\ 0) $ から $ (2,\ 0) $ を作る。コストが $ 2 $ かかる。 - この時点で $ S\ =\ \{(0,\ 0),\ (2,\ 0)\} $ である。 - 2番目の操作では $ (0,\ 0) $ から $ (0,\ 6) $ を作る。コストが $ 6 $ かかる。 - この時点で $ S\ =\ \{(0,\ 0),\ (2,\ 0),\ (0,\ 6)\} $ である。 - 3番目の操作では $ (2,\ 0) $ から $ (4,\ 0) $ を作る。コストが $ 2 $ かかる。 - この時点で $ S\ =\ \{(0,\ 0),\ (2,\ 0),\ (0,\ 6),\ (4,\ 0)\} $ である。 - 4番目の操作では $ (2,\ 0) $ から $ (2,\ 2) $ を作る。コストが $ 2 $ かかる。 - この時点で $ S\ =\ \{(0,\ 0),\ (2,\ 0),\ (0,\ 6),\ (4,\ 0),\ (2,\ 2)\} $ である。 - 5番目の操作では $ (2,\ 2) $ から $ (3,\ 2) $ を作る。コストが $ 1 $ かかる。 - この時点で $ S\ =\ \{(0,\ 0),\ (2,\ 0),\ (0,\ 6),\ (4,\ 0),\ (2,\ 2),\ (3,\ 2)\} $ である。 - 6番目の操作では $ (2,\ 2) $ から $ (2,\ 5) $ を作る。コストが $ 3 $ かかる。 - この時点で $ S\ =\ \{(0,\ 0),\ (2,\ 0),\ (0,\ 6),\ (4,\ 0),\ (2,\ 2),\ (3,\ 2),\ (2,\ 5)\} $ である。 最終的に $ S $ に $ (0,\ 6),\ (2,\ 5),\ (3,\ 2),\ (4,\ 0) $ がすべて含まれているので、この出力は AC と判定されます。 コストの総和は $ 16 $ です。$ C\ =\ 16,\ L\ =\ 6,\ N\ =\ 4 $ なので、スコアは $ \mathrm{round}\left(10^6\ \times\ \frac{6\ \times\ 4}{1\ +\ 16}\right)\ =\ 1411765 $ となります。