AT_ahc071_a [AHC071A] Brick Cover

CEO Takahashi has accidentally made several holes in a wall of the AtCoder Inc. office. Hoping to hide the damage before Vice President Aoki notices, Takahashi decides to stack bricks in front of the wall to conceal the holes. However, buying too many bricks might arouse Aoki's suspicion because of the expense. Help Takahashi arrange the bricks to hide all the holes at as little cost as possible.

There is a wall of height $ H $ cells and width $ W $ cells. Let $ (0,0) $ be the coordinates of the bottom-left cell, and let $ (x,y) $ be the coordinates of the cell located $ x $ cells to the right and $ y $ cells upward from there. There is a floor immediately below the bottom row of the wall, and $ K $ distinct cells $ (a_0,b_0),\ldots,(a_{K-1},b_{K-1}) $ contain holes. You want to stack bricks in front of this wall to cover every cell containing a hole. There are five types of bricks, each $ 1 $ cell high, with widths of $ 1,3,5,7,9 $ cells, and you can use any number of each type. A brick of width $ \ell $ costs $ c_\ell $ . Bricks cannot be rotated; placing a brick with its bottom-left corner at integer coordinates $ (x,y) $ covers the $ \ell $ cells $ (x,y),\ldots,(x+\ell-1,y) $ . Each brick stays in place by attaching a connector in the central cell of its bottom face to the floor or the brick directly below it. No support is required elsewhere, and the weight and center of gravity of bricks above it do not affect its stability. The arrangement must satisfy all of the following conditions. - Each brick fits within the wall. That is, a brick with bottom-left coordinates $ (x,y) $ and width $ \ell $ satisfies $ 0\leq x $ , $ x+\ell\leq W $ , and $ 0\leq y

Input is given from Standard Input in the following format. > $ W $ $ H $ $ K $ $ c_1 $ $ c_3 $ $ c_5 $ $ c_7 $ $ c_9 $ $ a_0 $ $ b_0 $ $ \vdots $ $ a_{K-1} $ $ b_{K-1} $ Each value satisfies the following constraints. - $ 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

Output to Standard Output in the following format. > $ M $ $ x_0 $ $ y_0 $ $ \ell_0 $ $ \vdots $ $ x_{M-1} $ $ y_{M-1} $ $ \ell_{M-1} $ Here, $ M $ is the number of bricks placed and must satisfy $ M\leq WH $ . Output the integer $ M $ on the first line, followed by $ M $ lines, the $ (i+1) $ -th of which contains the bottom-left coordinates $ (x_i,y_i) $ and width $ \ell_i $ of brick $ i $ , all as integers. $ \ell_i $ must be one of $ 1,3,5,7,9 $ . The bricks may be output in any order. You may output multiple solutions in the format above within the time limit. If you output multiple solutions, only the last one is used for scoring. Each solution represents a separate complete arrangement, rather than additions to a previously output solution. The web visualizer allows you to compare multiple solutions you have output. [Show example](https://img.atcoder.jp/ahc071/Wfu7FwbO.html?lang=en&seed=0&output=sample)

### Scoring Let $ M $ be the number of bricks used and $ \ell_0,\ldots,\ell_{M-1} $ be their widths, and define the cost $ C $ as follows. \\\[ C=\\sum\_{i=0}^{M-1}c\_{\\ell\_i} \\\] The cost of covering the entire wall with bricks of width $ 1 $ is $ WHc_1 $ . You receive the following score. \\\[ \\max(0,WHc\_1-C+1) \\\] There are 150 test cases, and the score of a submission is the sum of the scores for all test cases. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time. ### Input Generation Let $ \mathrm{rand}(L,R) $ be a function that generates an integer uniformly at random between $ L $ and $ R $ , inclusive. First, set $ c_1=5 $ , then generate $ c_\ell=\mathrm{rand}(2\ell-1,2\ell+4) $ for $ \ell=3,5,7,9 $ in this order. Next, generate the hole positions as follows. Until there are $ K $ holes, generate $ a=\mathrm{rand}(0,W-1) $ and then $ b=\mathrm{rand}(0,H-1) $ . If cell $ (a,b) $ does not already contain a hole, make a hole there; otherwise, discard the pair and generate $ a,b $ again. ### Tools (Input generator and visualizer) - [Web version](https://img.atcoder.jp/ahc071/Wfu7FwbO.html?lang=en): This is more powerful than the local version providing animations. - [Local version](https://img.atcoder.jp/ahc071/Wfu7FwbO.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). If it does not compile, please try `rustup update`. - [Pre-compiled binary for Windows](https://img.atcoder.jp/ahc071/Wfu7FwbO_windows.zip): If you are not familiar with the Rust language environment, please use this instead. Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited. The use of generative AI in this contest is prohibited, with limited exceptions. Please refer to [this post](https://atcoder.jp/posts/short-ahc-llm-rules-en) for further details.