AT_ahc071_a [AHC071A] Brick Cover

高橋社長は、うっかり AtCoder 社のオフィスの壁にいくつもの穴をあけてしまった。 青木副社長に見つかる前に何とかしたい高橋社長は、壁の前にレンガを積んで穴を隠すことにした。 ただし、レンガを買いすぎると、その出費から青木副社長に怪しまれるかもしれない。 できるだけ少ない費用ですべての穴を隠せるよう、レンガの配置を考えてほしい。

高さ $ H $ マス、幅 $ W $ マスの壁がある。 左下のマスの座標を $ (0,0) $ とし、そこから右方向に $ x $ マス、上方向に $ y $ マス進んだ先のマスの座標を $ (x,y) $ とする。 壁の最下段のすぐ下には床があり、 $ K $ 個の異なるマス $ (a_0,b_0),\ldots,(a_{K-1},b_{K-1}) $ に穴があいている。 あなたは、この壁の手前にレンガを積み上げ、すべての穴のあいたマスを覆いたい。 レンガは高さが $ 1 $ マスで、幅が $ 1,3,5,7,9 $ マスの $ 5 $ 種類あり、それぞれ何個でも使用できる。 幅 $ \ell $ のレンガ $ 1 $ 個の代金は $ c_\ell $ である。 レンガは回転させることができず、左下の座標を整数座標 $ (x,y) $ として配置すると、 $ (x,y),\ldots,(x+\ell-1,y) $ の $ \ell $ 個のマスを覆う。 各レンガは、底面の中央の $ 1 $ マスにある接続部を、床または直下のレンガに固定することで姿勢を保つ。 中央以外の部分が支えられている必要はなく、上に載るレンガの重さや重心は姿勢の維持に影響しない。 配置は、以下の条件をすべて満たさなければならない。 - 各レンガは壁内に収まる。 すなわち、左下の座標が $ (x,y) $ 、幅が $ \ell $ のレンガについて、 $ 0\leq x $ 、 $ x+\ell\leq W $ 、 $ 0\leq y

入力は以下の形式で標準入力から与えられる。 > $ W $ $ H $ $ K $ $ c_1 $ $ c_3 $ $ c_5 $ $ c_7 $ $ c_9 $ $ a_0 $ $ b_0 $ $ \vdots $ $ a_{K-1} $ $ b_{K-1} $ 各値は以下の制約を満たす。 - $ W=60 $ - $ H=40 $ - $ K=120 $ - $ c_1=5 $ - $ 2\ell-1\leq c_\ell\leq 2\ell+4 $ ( $ \ell=3,5,7,9 $ ) - $ 0\leq a_j

以下の形式で標準出力に出力せよ。 > $ M $ $ x_0 $ $ y_0 $ $ \ell_0 $ $ \vdots $ $ x_{M-1} $ $ y_{M-1} $ $ \ell_{M-1} $ ここで、 $ M $ は配置するレンガの個数であり、 $ M\leq WH $ を満たさなければならない。 最初の行に $ M $ を整数で出力し、続く $ M $ 行のうち $ i+1 $ 行目に、レンガ $ i $ の左下の座標 $ (x_i,y_i) $ と幅 $ \ell_i $ を整数で出力せよ。 $ \ell_i $ は $ 1,3,5,7,9 $ のいずれかでなければならない。 出力するレンガの順序は任意である。 実行時間制限内であれば、上記の形式の解を複数回出力してもよい。 複数回出力した場合、最後に出力された解のみが採点に用いられる。 各解は独立した完成配置を表し、先に出力した解へのレンガの追加を表すものではない。 Web版ビジュアライザでは、出力した複数の解を比較することができる。 [例を見る](https://img.atcoder.jp/ahc071/Wfu7FwbO.html?lang=ja&seed=0&output=sample)

### 得点 使用するレンガの個数を $ M $ 、各レンガの幅を $ \ell_0,\ldots,\ell_{M-1} $ とし、費用 $ C $ を以下で定義する。 \\\[ C=\\sum\_{i=0}^{M-1}c\_{\\ell\_i} \\\] 壁全体を幅 $ 1 $ のレンガで覆うときの費用は $ WHc_1 $ である。 このとき、以下の得点が得られる。 \\\[ \\max(0,WHc\_1-C+1) \\\] 合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定が WA や TLE となり、提出の得点は 0 点となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 $ \mathrm{rand}(L,R) $ を、 $ L $ 以上 $ R $ 以下の整数から一様ランダムに値を生成する関数とする。 まず、 $ c_1=5 $ とし、 $ \ell=3,5,7,9 $ の順に $ c_\ell=\mathrm{rand}(2\ell-1,2\ell+4) $ を生成する。 次に、穴の位置を以下の手順で生成する。 穴の個数が $ K $ 個になるまで、 $ a=\mathrm{rand}(0,W-1) $ 、 $ b=\mathrm{rand}(0,H-1) $ の順に値を生成する。 マス $ (a,b) $ にまだ穴があいていなければ穴をあけ、すでに穴があいていればその組を捨てて再び $ a,b $ を生成する。 ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc071/Wfu7FwbO.html?lang=ja): ローカル版より高性能でアニメーション表示が可能です。 - [ローカル版](https://img.atcoder.jp/ahc071/Wfu7FwbO.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 コンパイルが通らない場合は `rustup update` をお試し下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc071/Wfu7FwbO_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。 ご注意下さい。 本コンテストでは、生成AIの利用は一部の例外を除き禁止されています。 詳細は[こちらの記事](https://atcoder.jp/posts/short-ahc-llm-rules-ja)をご確認ください。