AT_ahc049_a [AHC049A] Durability-Constrained Transport

AtCoder Inc. has decided to move to a new office. To keep costs down, instead of hiring a moving company, CEO Takahashi will do the moving himself. The old office is filled with a large number of cardboard boxes laid out on the floor, and all of them must be transported to the entrance. Boxes can be stacked and carried multiple at once, but if stacked too heavily, they may collapse under their own weight. Your task is to find a way to safely carry all the boxes to the entrance using as few moves as possible.

There is an office consisting of $ N \times N $ squares. Let $ (0, 0) $ be the coordinates of the top-left square, and $ (i, j) $ be the coordinates of the square located $ i $ squares down and $ j $ squares to the right from there. The office entrance is located at square $ (0, 0) $ . Initially, one cardboard box is placed in every square except the entrance. Each cardboard box has two numerical values: **weight** and **durability**. The box at square $ (i, j) $ has a weight of $ w_{i,j} $ and a durability of $ d_{i,j} $ . Cardboard boxes can be stacked vertically to carry multiple boxes at once. Starting from the initial position $ (0,0) $ , Takahashi’s goal is to carry all the boxes out of the office by repeatedly performing the following operations: 1. Pick up the cardboard box at the current position. If already holding boxes, place the new one on top. This operation cannot be performed if there is no box at the current position. 2. Place the topmost box in hand at the current position. This cannot be performed if there is already a box in that square. 3. Move to an adjacent square in one of the four directions: up, down, left, or right. It is allowed to move onto squares that have a box, but moving outside the $ N \times N $ area is not allowed. Takahashi is very strong and can carry any number of boxes regardless of total weight. However, the durability of boxes he is holding decreases when he moves (operation 3). A box with durability reduced to 0 or below will be crushed and judged as WA. The amount by which a box’s durability decreases is equal to the total weight of all boxes stacked above it. Specifically, if the boxes currently held have weights $ w_1, w_2, \ldots, w_n $ from bottom to top, then the $ i $ -th box from the bottom ( $ 1 \le i \le n $ ) will lose $ \sum_{j=i+1}^n w_j $ durability per move. Durability decreases only during movement (operation 3). It does not change during picking up or placing a box (operations 1 and 2). Durability also does not recover after placing a box on the floor. When moving to the entrance at $ (0, 0) $ using operation 3, all boxes currently held are carried out of the office. You may perform at most $ 2 \times N^3 $ operations in total. Your task is to carry out all the cardboard boxes using as few moves as possible.

Input is given from Standard Input in the following format: > $ N $ $ w_{0,0} $ $ \cdots $ $ w_{0,N-1} $ $ \vdots $ $ w_{N-1,0} $ $ \cdots $ $ w_{N-1,N-1} $ $ d_{0,0} $ $ \cdots $ $ d_{0,N-1} $ $ \vdots $ $ d_{N-1,0} $ $ \cdots $ $ d_{N-1,N-1} $ - In all test cases, $ N $ is fixed at 20. - $ w_{i,j} $ is an integer representing the weight of the cardboard box placed at square $ (i, j) $ . Since there is no box at square $ (0,0) $ , we have $ w_{0,0} = 0 $ . For all other squares, $ 1 \leq w_{i,j} \leq 10^3 $ . - $ d_{i,j} $ is an integer representing the durability of the cardboard box placed at square $ (i, j) $ . At square $ (0,0) $ , $ d_{0,0} = 0 $ . For all other squares, $ 10 \leq d_{i,j} \leq 3\times 10^4 $ .

Let the operation performed in turn $ t $ be represented by a single character $ a_t $ as follows: 1. If performing operation 1: `1` 2. If performing operation 2: `2` 3. If performing operation 3: Up: `U` Down: `D` Left: `L` Right: `R` Let $ L $ be the number of operations. Then, output to Standard Output in the following format: > $ a_0 $ $ \vdots $ $ a_{L-1} $ [Show example](https://img.atcoder.jp/ahc049/LDUZCjLO.html?lang=en&seed=0&output=sample)

### Scoring Let $ T $ be the number of times operation 3 (movement) is performed, and let $ R $ be the number of cardboard boxes remaining in the office. The score is calculated as follows: - If $ R > 0 $ : $ N^2 - R $ - If $ R = 0 $ : $ N^2 + 2 \times N^3 - T $ Here, $ T $ counts only the number of times operation 3 (movement) is performed; operations 1 (pick up) and 2 (place) are not included in $ T $ . However, the limit on the total number of operations (at most $ 2 \times N^3 $ ) applies to all operations. There are $ 150 $ test cases, and the score of a submission is the total score for each test case. 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 - $ \mathrm{rand\_double}(L,U) $ : Generates a uniformly random real number between $ L $ and $ U $ . #### Generation of $ w $ For every square $ (i, j) $ except $ (0, 0) $ , we generate $ w_{i,j} $ as $ \mathrm{round}(\mathrm{rand\_double}(1, \sqrt{1000})^2) $ . #### Generation of $ d $ For every square $ (i, j) $ except $ (0, 0) $ , we generate $ d_{i,j} $ as $ \mathrm{round}(w_{i,j} \times \mathrm{rand\_double}(10, 30)) $ . ### Tools (Input generator and visualizer) - [Web version](https://img.atcoder.jp/ahc049/LDUZCjLO.html?lang=en): This is more powerful than the local version providing animations and manual play. - [Local version](https://img.atcoder.jp/ahc049/LDUZCjLO.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). - [Pre-compiled binary for Windows](https://img.atcoder.jp/ahc049/LDUZCjLO_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.