AT_ahc048_a [AHC048A] Mixing on the Palette

Painter Takahashi is working on a new series of watercolor paintings. His works are highly praised for their delicate use of color, and he is especially particular about color blending. As his assistant, you are tasked with the important role of mixing and delivering the exact colors he requests, on the spot. Because the paints used are expensive, you are expected to mix the colors with as little waste as possible. Fortunately, a list of the required colors has been provided in advance. You are asked to produce these colors in the given order, as accurately as possible and with as little waste as you can.

A paint color is represented as a three-dimensional vector $ (C, M, Y) $ consisting of cyan ( $ C $ ), magenta ( $ M $ ), and yellow ( $ Y $ ), where $ 0 \leq C, M, Y \leq 1 $ . When you mix $ v_1 $ grams of paint with color $ p_1 = (C_1, M_1, Y_1) $ and $ v_2 $ grams of paint with color $ p_2 = (C_2, M_2, Y_2) $ , you obtain $ (v_1 + v_2) $ grams of paint with color $ \frac{v_1 \cdot p_1 + v_2 \cdot p_2}{v_1 + v_2} $ . v₁ = 4 p₁ = (1, 0, 0) + v₂ = 6 p₂ = (0, 1, 0) = v₁ + v₂ = 10 p = (0.4, 0.6, 0) You own $ K $ types of tube paints. The $ i $ -th tube has the color $ (C^{\mathrm{own}}_i, M^{\mathrm{own}}_i, Y^{\mathrm{own}}_i) $ . Using 1 gram from any tube incurs a cost of $ D $ . Your goal is to use these tubes to produce $ H $ target colors, each exactly 1 gram, in the specified order and deliver them to the painter. The $ i $ -th target color is $ (C^{\mathrm{target}}_i, M^{\mathrm{target}}_i, Y^{\mathrm{target}}_i) $ . The order of creation is fixed and cannot be changed. The palette used for mixing paint is composed of an $ N \times N $ grid of cells. The top-left cell is at coordinate $ (0, 0) $ , and the cell at $ i $ rows down and $ j $ columns to the right is $ (i, j) $ . Each cell is equipped with movable dividers between its adjacent cells in the up, down, left, and right directions. You may freely configure the initial state of these dividers. If the divider between two adjacent cells is lowered, the two cells are said to be **connected**. A **well** is defined as a set of connected cells reachable via such connections. By moving the dividers, you can merge multiple wells or split a well into multiple separate ones. Each well can contain at most one color of paint, and a well consisting of $ k $ cells can hold up to $ k $ grams of paint. Initially, all wells are empty. You may perform the following operations for up to $ T $ turns: 1. Choose any cell and any tube, and pour 1 gram of paint from the tube into the well that the cell belongs to. Let $ w $ be the remaining capacity of the well. Then, $ \min(w, 1) $ grams will actually be mixed, and the remaining $ 1 - \min(w, 1) $ grams will be immediately discarded. 2. Choose any cell and take 1 gram of paint from the well that the cell belongs to, and deliver it to the painter. You cannot choose a cell whose well contains less than 1 gram of paint. 3. Choose any cell and discard 1 gram of paint from the well that the cell belongs to. If less than 1 gram remains, discard all of it. 4. Choose two adjacent cells $ s $ and $ t $ and toggle the divider between them. - If lowering the divider merges two wells, the paints are mixed into a single color. - If raising the divider splits a well into two, the paint is divided proportionally to the capacities. That is, if the well originally contained $ v $ grams of paint, and the capacities of the resulting wells are $ v_s $ and $ v_t $ for the $ s $ and $ t $ sides respectively, then the paint remaining on the $ s $ side will be $ v \times \frac{v_s}{v_s + v_t} $ , and the $ t $ side will have $ v \times \frac{v_t}{v_s + v_t} $ . You must perform **operation 2 exactly $ H $ times**. If you perform it fewer or more than $ H $ times, the result will be WA. #### About Floating-Point Precision Since paint quantities are fractional values, it is difficult to strictly determine whether a well contains “at least 1 gram” for operation 2. Therefore, the judge system manages paint quantities using double-precision floating-point numbers, and the validity of operation 2 and the extracted amount are determined based on the internal value $ v $ (in grams) as follows: - **Validity of operation** - If $ v < 1 - 10^{-6} $ : The well is considered to contain “less than 1 gram,” and operation 2 cannot be performed. - If $ v \geq 1 - 10^{-6} $ : The well is considered to contain “at least 1 gram,” and operation 2 can be performed. - **Amount extracted** - If $ v \geq 1 $ : Exactly 1 gram is extracted. - If $ 1 - 10^{-6} \leq v < 1 $ : All of the remaining paint in the well is extracted. The provided tools are implemented to behave **exactly the same** as the judge system.

The input is given from Standard Input in the following format: > $ N $ $ K $ $ H $ $ T $ $ D $ $ C_0^{\mathrm{own}} $ $ M_0^{\mathrm{own}} $ $ Y_0^{\mathrm{own}} $ $ \vdots $ $ C_{K-1}^{\mathrm{own}} $ $ M_{K-1}^{\mathrm{own}} $ $ Y_{K-1}^{\mathrm{own}} $ $ C_0^{\mathrm{target}} $ $ M_0^{\mathrm{target}} $ $ Y_0^{\mathrm{target}} $ $ \vdots $ $ C_{H-1}^{\mathrm{target}} $ $ M_{H-1}^{\mathrm{target}} $ $ Y_{H-1}^{\mathrm{target}} $ - The palette size $ N $ is fixed to $ N = 20 $ for all test cases. - The number of tube paint types $ K $ satisfies $ 4 \leq K \leq 20 $ . - The number of target colors $ H $ is fixed to $ H = 1000 $ for all test cases. - The maximum number of turns $ T $ satisfies $ 4000 \leq T \leq 64000 $ . - The cost $ D $ for using 1 gram from a tube satisfies $ 10 \leq D \leq 10000 $ .

First, output the initial configuration of dividers in the following format to standard output: > $ v_{0,0} $ $ \cdots $ $ v_{0,N-2} $ $ \vdots $ $ v_{N-1,0} $ $ \cdots $ $ v_{N-1,N-2} $ $ h_{0,0} $ $ \cdots $ $ h_{0,N-1} $ $ \vdots $ $ h_{N-2,0} $ $ \cdots $ $ h_{N-2,N-1} $ - $ v_{i,j} $ represents the state of the vertical divider between cell $ (i, j) $ and cell $ (i, j+1) $ . If $ v_{i,j} = 0 $ , the divider is lowered. If $ v_{i,j} = 1 $ , the divider is raised. - $ h_{i,j} $ represents the state of the horizontal divider between cell $ (i, j) $ and cell $ (i+1, j) $ . If $ h_{i,j} = 0 $ , the divider is lowered. If $ h_{i,j} = 1 $ , the divider is raised. Next, output up to $ T $ lines of operations. The $ t $ -th line specifies the operation to be performed on turn $ t $ in one of the following formats: - To add 1 gram of paint from tube $ k $ ( $ 0 \leq k \leq K-1 $ ) to the well containing cell $ (i, j) $ : > 1 $ i $ $ j $ $ k $ - To extract 1 gram of paint from the well containing cell $ (i, j) $ and deliver it to the painter: > 2 $ i $ $ j $ - To discard 1 gram of paint from the well containing cell $ (i, j) $ : > 3 $ i $ $ j $ - To toggle the divider between adjacent cells $ (i_1, j_1) $ and $ (i_2, j_2) $ : > 4 $ i_1 $ $ j_1 $ $ i_2 $ $ j_2 $ [Show example](https://img.atcoder.jp/ahc048/lI5DXOAV.html?lang=en&seed=0&output=sample)

### Scoring Let the color of the paint delivered to the painter in the $ i $ -th execution of operation 2 be $ (C_i^\mathrm{made}, M_i^\mathrm{made}, Y_i^\mathrm{made}) $ . The total error $ E $ is defined as follows: \\\[ E = \\sum\_{i=0}^{H-1} \\sqrt{(C^{\\mathrm{target}}\_i - C^{\\mathrm{made}}\_i)^2 + (M^{\\mathrm{target}}\_i - M^{\\mathrm{made}}\_i)^2 + (Y^{\\mathrm{target}}\_i - Y^{\\mathrm{made}}\_i)^2} \\\] Let $ V $ be the number of times operation 1 was performed. Then, your **absolute score** is calculated as: \\\[ 1 + D \\cdot (V - H) + \\mathrm{round}(10^4 \\times E) \\\] **The lower the absolute score, the better.** For each test case, we compute the **relative score** $ \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}) $ , where YOUR is your absolute score and MIN is the lowest absolute score among all competitors obtained on that test case. The score of the submission is the sum of the relative scores. The final ranking will be determined by the system test with more inputs which will be run after the contest is over. In both the provisional/system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the score for those test cases will be zero, and your submission will be excluded from the MIN calculation for those test cases. The system test will be performed only for **the last submission which received a result other than CE** . Be careful not to make a mistake in the final submission. #### Number of test cases - Provisional test: 50 - System test: 2000. We will publish [seeds.txt](https://img.atcoder.jp/ahc048/seeds.txt) (sha256=e93b5367e87f49c8fe325dbeb0f8daa331d23481c1eb533ff032c7978e39ae04) after the contest is over. #### About relative evaluation system In both the provisional/system test, the standings will be calculated using only the last submission which received a result other than CE. Only the last submissions are used to calculate the MIN for each test case when calculating the relative scores. The scores shown in the standings are relative, and whenever a new submission arrives, all relative scores are recalculated. On the other hand, the score for each submission shown on the submissions page is the sum of the absolute score for each test case, and the relative scores are not shown. In order to know the relative score of submission other than the latest one in the current standings, you need to resubmit it. If your submission produces illegal output or exceeds the time limit for some test cases, the score shown on the submissions page will be 0, but the standings show the sum of the relative scores for the test cases that were answered correctly. #### About execution time Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in TLE in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time. ### Input Generation - $ \mathrm{rand}(L,U) $ : Generates a uniformly random integer between $ L $ and $ U $ , inclusive. - $ \mathrm{rand\_double}(L,U) $ : Generates a uniformly random real number between $ L $ and $ U $ . #### Generation of $ N $ , $ K $ , $ H $ , $ T $ , and $ D $ - $ N = 20 $ - $ K = \mathrm{rand}(4,20) $ - $ H = 1000 $ - $ T = \mathrm{round}(4000 \times 2^{\mathrm{rand\_double}(0,4)}) $ - $ D = \mathrm{round}(10^{\mathrm{rand\_double}(1,4)}) $ #### Generation of tube paint $ (C^{\mathrm{own}}, M^{\mathrm{own}}, Y^{\mathrm{own}}) $ For each $ i $ , generate independently as follows: - $ C_i^{\mathrm{own}} = \mathrm{rand}(0,10^5) \times 10^{-5} $ - $ M_i^{\mathrm{own}} = \mathrm{rand}(0,10^5) \times 10^{-5} $ - $ Y_i^{\mathrm{own}} = \mathrm{rand}(0,10^5) \times 10^{-5} $ #### Generation of target colors $ (C^{\mathrm{target}}, M^{\mathrm{target}}, Y^{\mathrm{target}}) $ The target colors are generated independently for each $ i $ as follows: 1. Generate $ K $ values $ x_0, \dots, x_{K-1} $ using $ x_k = -\ln \mathrm{rand\_double}(0, 1) $ , where $ \ln $ denotes the natural logarithm. 2. Normalize: Let $ x_k' = x_k \Big/ \sum_{j=0}^{K-1} x_j $ . 3. Compute the components of the target color as follows: \\\[ C\_i^{\\mathrm{target}} = \\mathrm{round}\\left(10^5 \\times \\sum\_{k=0}^{K-1} x\_k' C\_k^\\mathrm{own}\\right) \\times 10^{-5} \\\] \\\[ M\_i^{\\mathrm{target}} = \\mathrm{round}\\left(10^5 \\times \\sum\_{k=0}^{K-1} x\_k' M\_k^\\mathrm{own}\\right) \\times 10^{-5} \\\] \\\[ Y\_i^{\\mathrm{target}} = \\mathrm{round}\\left(10^5 \\times \\sum\_{k=0}^{K-1} x\_k' Y\_k^\\mathrm{own}\\right) \\times 10^{-5} \\\] ### Tools (Input generator and visualizer) - [Web version](https://img.atcoder.jp/ahc048/lI5DXOAV.html?lang=en): This is more powerful than the local version providing animations. - [Local version](https://img.atcoder.jp/ahc048/lI5DXOAV.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). - [Pre-compiled binary for Windows](https://img.atcoder.jp/ahc048/lI5DXOAV_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.