AT_masters2026_qual_a Periodic Patrol Automata (A)

AtCoder Inc. is developing robots to guard its office. Each robot is controlled by a [finite-state automaton](https://en.wikipedia.org/wiki/Finite-state_machine) that changes its state and actions depending on whether there is a wall in front of it. The required cost varies depending on the number of states in the automaton, the number of robots to be introduced, and the number of new walls to be installed. Please find a method with as low a cost as possible such that the entire office is patrolled periodically.

There is an $ N\times N $ grid. Let the coordinates of the top-left cell be $ (0,0) $ , and define the coordinates of the cell reached by moving $ i $ cells downward and $ j $ cells to the right from there as $ (i,j) $ . The outer boundary of the $ N\times N $ grid is surrounded by walls, and there may also be walls between adjacent cells. Up to $ N^2 $ robots can be introduced. For each robot, up to $ 4N^2 $ internal states can be defined. Each robot is controlled by an automaton that, depending on whether there is a wall in front of it (i.e., whether there is a wall between the current cell and the cell one step ahead in the current direction) and its current internal state, determines an action among going forward, turning right, and turning left, as well as the next internal state. Going forward (`F`) moves one cell forward in the current direction, and the direction does not change. Turning right (`R`) and turning left (`L`) refer to changing direction in place without moving to another cell. One step of operation is performed in the following order. First, from the current (position, direction, internal state), the robot determines whether there is a wall in front. Next, it determines the action and the next state. Then it performs the action, and finally it updates the internal state to the next state. Let $ m_k $ be the number of internal states of the automaton that controls the $ k $ -th robot. You may choose $ m_k $ arbitrarily. Then, for each state $ s=0,1,\cdots,m_k-1 $ , specify the following. - $ a_{k,s,0} $ : Which of turning right (`R`), turning left (`L`), or going forward (`F`) to perform when there is no wall in front. - $ b_{k,s,0} $ : The next state number when there is no wall in front. - $ a_{k,s,1} $ : Which of turning right (`R`) or turning left (`L`) to perform when there is a wall in front. Going forward (`F`) cannot be chosen. - $ b_{k,s,1} $ : The next state number when there is a wall in front. #### Example > Consider the following automaton with 2 internal states. > > $ s $ $ a_{k,s,0} $ $ b_{k,s,0} $ $ a_{k,s,1} $ $ b_{k,s,1} $ 0 F 0 R 1 1 R 0 R 0  > > This automaton operates as follows. > > - When the internal state is 0, it goes forward as long as there is no wall in front, and if there is a wall in front, it turns right and transitions to internal state 1. > - When the internal state is 1, it turns right regardless of whether there is a wall in front, and transitions to internal state 0. > > In other words, it repeats the behavior of going forward as long as there is no wall in front, and making a U-turn just in front of a wall. Next, for each robot $ k $ , determine its position $ (i_k,j_k) $ and direction $ d_k $ in the initial placement (up: `U`, down: `D`, left: `L`, right: `R`). The initial value of the internal state is $ 0 $ . Robots do not interfere with each other, and multiple robots may occupy the same cell. Finally, install new walls. A wall can be installed between any two adjacent cells. You may specify a position where a wall already exists, but nothing happens other than increasing the cost. It is allowed for the board to become disconnected due to newly installed walls. For each robot, the set of (position, direction, internal state) is finite, and the next-time (position, direction, internal state) corresponding to the same set is uniquely determined. Therefore, after some time has passed, it will inevitably enter periodic behavior. Define the cells that the robot visits during this periodic behavior as the cells patrolled by that robot. Cells that are visited only before entering periodic behavior are not included in the cells patrolled. Let $ K $ be the number of robots to be introduced, let $ M=\sum_k m_k $ be the total number of internal states over all robots, and let $ W $ be the number of newly installed walls specified in the output (the number of `1`s in the output). Given the coefficients $ A_K $ , $ A_M $ , and $ A_W $ provided in the input, define the introduction cost $ V $ as follows. \\\[ V = A\_K \\times (K-1) + A\_M \\times M + A\_W \\times W \\\] Find a method with as low an introduction cost as possible such that every cell becomes a cell patrolled by at least one robot. If there exists a cell that does not become a patrolled cell, it will be judged as WA.

The input is given from Standard Input in the following format. > $ N $ $ A_K $ $ A_M $ $ A_W $ $ 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} $ - The board size $ N $ is fixed to $ N=20 $ for all test cases. - The coefficients $ A_K $ , $ A_M $ , and $ A_W $ of the introduction cost are integers between $ 0 $ and $ 1000 $ , inclusive. - $ v_{i,0} \cdots v_{i,N-2} $ is a string of length $ N-1 $ consisting of `0` and `1`, and the $ j $ -th character $ v_{i,j} $ indicates whether there is (`1`) or is not (`0`) a wall between cell $ (i, j) $ and cell $ (i, j+1) $ . - $ h_{i,0} \cdots h_{i,N-1} $ is a string of length $ N $ consisting of `0` and `1`, and the $ j $ -th character $ h_{i,j} $ indicates whether there is (`1`) or is not (`0`) a wall between cell $ (i, j) $ and cell $ (i+1, j) $ . - In the initial state, it is guaranteed that all cells are mutually reachable.

Print to Standard Output in the following format. > $ K $ $ m_0 $ $ i_0 $ $ j_0 $ $ d_0 $ $ a_{0,0,0} $ $ b_{0,0,0} $ $ a_{0,0,1} $ $ b_{0,0,1} $ $ \vdots $ $ a_{0,m_0-1,0} $ $ b_{0,m_0-1,0} $ $ a_{0,m_0-1,1} $ $ b_{0,m_0-1,1} $ $ \vdots $ $ m_{K-1} $ $ i_{K-1} $ $ j_{K-1} $ $ d_{K-1} $ $ a_{K-1,0,0} $ $ b_{K-1,0,0} $ $ a_{K-1,0,1} $ $ b_{K-1,0,1} $ $ \vdots $ $ a_{K-1,m_{K-1}-1,0} $ $ b_{K-1,m_{K-1}-1,0} $ $ a_{K-1,m_{K-1}-1,1} $ $ b_{K-1,m_{K-1}-1,1} $ $ 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}' $ - $ K $ is the number of robots to be developed, and it must satisfy $ 1\leq K\leq N^2 $ . - $ m_k $ is the number of internal states of the $ k $ -th robot, and it must satisfy $ 1\leq m_k\leq 4N^2 $ . - $ (i_k,j_k) $ is the initial position of the $ k $ -th robot, and it must satisfy $ 0\leq i_k,j_k\leq N-1 $ . - $ d_k $ is the initial direction of the $ k $ -th robot, and is one of the characters up: `U`, down: `D`, left: `L`, right: `R`. - For each robot $ k $ , you must output exactly $ m_k $ lines in the order of internal state $ s=0,1,\dots,m_k-1 $ . - $ a_{k,s,0} $ and $ a_{k,s,1} $ represent the action of robot $ k $ when its internal state is $ s $ . For the cases where there is no wall in front and where there is a wall in front, respectively, specify one of turn right: `R`, turn left: `L`, or go forward: `F`. However, $ a_{k,s,1} $ must not be `F`. - $ b_{k,s,0} $ and $ b_{k,s,1} $ represent the next internal state number when robot $ k $ is in internal state $ s $ . For the cases where there is no wall in front and where there is a wall in front, respectively, they must satisfy $ 0\leq b_{k,s,0}, b_{k,s,1}\leq m_k-1 $ . - $ v_{i,0}' \cdots v_{i,N-2}' $ is a string of length $ N-1 $ consisting of `0` and `1`, and the $ j $ -th character $ v_{i,j}' $ indicates whether to install (`1`) or not install (`0`) a new wall between cell $ (i, j) $ and cell $ (i, j+1) $ . - $ h_{i,0}' \cdots h_{i,N-1}' $ is a string of length $ N $ consisting of `0` and `1`, and the $ j $ -th character $ h_{i,j}' $ indicates whether to install (`1`) or not install (`0`) a new wall between cell $ (i, j) $ and cell $ (i+1, j) $ . - The board may become disconnected due to wall installation.

### Scoring When the introduction cost is $ V $ , you obtain the following score. \\\[ 1+\\mathrm{round}\\left(10^6\\times \\max\\left(0,\\log\_2 \\frac{A\_K (N^2-1) + A\_M N^2}{V}\\right)\\right) \\\] Depending on the coefficients $ A_K $ , $ A_M $ , and $ A_W $ , the problem is divided into three subproblems: A, B, and C. Each subproblem contains 150 test cases, and the total score for a submission to that subproblem is the sum of the scores from all test cases in it. 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 final ranking is determined by the sum of the highest scores obtained for each subproblem, and there will be no system test after the contest. If more than one team gets the same score, they will be ranked in the same place regardless of the submission time. ### Sample Solution A sample solution in Python is shown. In this program, one robot that keeps turning right in place is placed on each cell. ``` import sys input = sys.stdin.readline N, AK, AM, AW = map(int, input().split()) wall_v = [input().strip() for _ in range(N)] wall_h = [input().strip() for _ in range(N - 1)] K = N * N print(K) for i in range(N): for j in range(N): m = 1 d = 'U' print(m, i, j, d) print('R 0 R 0') for _ in range(N): print('0' * (N - 1)) for _ in range(N - 1): print('0' * N) ``` ### Input Generation For each of the tasks A, B, and C, the coefficients are generated uniformly at random from the ranges (closed intervals) listed in the following table. Task $ A_K $ $ A_M $ $ A_W $ A $ [0,0] $ $ [1,1] $ $ [1000,1000] $ B $ [1000,1000] $ $ [1,10] $ $ [1,10] $ C $ [1000,1000] $ $ [1,1] $ $ [1000,1000] $ #### Generation of walls Let $ \mathrm{rand}(L, U) $ be a function that generates an integer uniformly at random between $ L $ and $ U $ , inclusive. First, generate the number of vertical wall generations $ X=\mathrm{rand}(1,6) $ and the number of horizontal wall generations $ Y=\mathrm{rand}(1,6) $ . Starting from a state with no walls at all, generate walls as follows. Repeat the following operation $ X $ times. 1. Randomly decide whether to generate the wall upward or downward. 2. Generate the wall length by $ L = \mathrm{rand}(5, 15) $ . 3. Choose the starting point $ (i, j) $ by $ i = \mathrm{rand}(0, N-1),\ j = \mathrm{rand}(0, N-2) $ . 4. If the direction is upward, set $ v_{i-L+1, j}, \cdots, v_{i, j} $ to `1`; if the direction is downward, set $ v_{i, j}, \cdots, v_{i+L-1, j} $ to `1`. Terms whose indices go out of the board range are ignored. Repeat the following operation $ Y $ times. 1. Randomly decide whether to generate the wall from the left or from the right. 2. Generate the wall length by $ L = \mathrm{rand}(5, 15) $ . 3. Choose the starting point $ (i, j) $ by $ i = \mathrm{rand}(0, N-2),\ j = \mathrm{rand}(0, N-1) $ . 4. If the direction is leftward, set $ h_{i, j-L+1}, \cdots, h_{i, j} $ to `1`; if the direction is rightward, set $ h_{i, j}, \cdots, h_{i, j+L-1} $ to `1`. Terms whose indices go out of the board range are ignored. For the generated walls, check whether all cells are reachable. If some cells are unreachable, reset the walls and redo the wall generation (do not regenerate $ X $ and $ Y $ ). ### Tools (Input generator and score calculation) - [Local version](https://img.atcoder.jp/masters2026-qual/Cy1HtjaW.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). - [Pre-compiled binary for Windows](https://img.atcoder.jp/masters2026-qual/Cy1HtjaW_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 outside of the team during the contest is prohibited.