P16188 [ZJOI2014] 2048

$2048$ is a very popular small game recently. First, we introduce the rules of the real game: the $2048$ game consists of a $4 \times 4$ matrix. Each position (cell) can contain at most one tile, and each tile is labeled with a number that is a power of $2$. In each turn, the player chooses a **legal** direction from up, down, left, and right (the legality will be explained later). All tiles move **as far as possible** in that direction until they hit the boundary, while keeping their order. If tiles that **push against each other** (i.e., **adjacent** and their relative positions are **parallel** to the chosen direction) have the same number, they immediately merge into one tile, and the disappearing tile immediately frees its cell. In each turn, each tile can be merged **at most once**, and the merge order gives priority to the tile that is **closer to the front** along the chosen direction. A direction is **legal** if and only if at least one tile is moved or merged in that direction, so after the operation, there is at least one empty cell in the matrix. Before the game starts or between turns, the game program randomly generates a tile labeled $2$ or $4$ in an empty cell. When a $2048$ tile is formed on the board, the game ends and the player wins. If the player cannot make any legal move, the game ends and the player loses. Now, we want the AI to get as high a score as possible. Note that **the rules in this problem are different from the real game**. In the game, the player does not know the position and value of the randomly generated tile. In this problem, we **give the random algorithm**, and each time we **only generate tiles labeled $2$**, hoping to obtain a fairly high score. Example of the game rules: After the state shown in the left figure appears, the player chooses to move left. The three $4$ tiles below will become one $8$ and one $4$. Since the left two $4$ tiles are closer to the moving direction (left), they should merge into the leftmost $8$ and the second-leftmost $4$ (see the right figure). From the figures, you can see that the game program randomly generated a $2$ in the bottom-right corner between turns:  The random algorithm is as follows: Given a random seed $seed$, and a constant $MUL = 8221$, a signed 32-bit random integer sequence $seq$ is generated by: $$seq_0 = seed$$ $$seq_i = seq_{i-1} \times MUL + (seq_{i-1} >> 16) (i \ge 1)$$ Here, the symbol $>>$ means signed right shift. When the result of addition/subtraction is $\ge 2^{31}$ (or $< −2^{31}$), it automatically becomes the equal negative number (or positive number) under modulo $2^{32}$. The random numbers needed by the 2048 game are integers from $0 \sim 15$, representing tiles numbered from left to right and from top to bottom in order (see the figure below). Each time a tile needs to be randomly generated, we take numbers from the random sequence one by one and take modulo $16$, until we get a number that corresponds to an empty cell (not a cell already occupied by a tile). The next time we take a random number, we should start from the one after the previously chosen number. The first random number is $seq_1$. Typical code to generate the above random sequence in C ~~and Pascal~~ is as follows: ```cpp int MUL = 8221; int seq; void initSeed(int seed) { seq = seed; } int getRand() { return (seq = (seq * MUL) + (seq >> 16)) & 15; } ``` Here we specify a set of random seeds: the $i$-th test point uses the random seed with value $i$ ($i = 1 \sim 20$), and the corresponding output files are `20481.out~204820.out`. In the output files, please include, in order, a sequence of legal operations to obtain tiles with as large labels as possible. During scoring, the final state after execution will be used for evaluation. The additional file `simulate(.exe)` can check your output file and simulate it, printing the final state to the console. Usage: call `simulate [filename: 2048*.out]` in `terminal` or `cmd.exe`.

One line with one number indicating the test point index.

You may submit twenty files `20481.out ~ 204820.out`, or submit table-lookup code (note Luogu’s code length limit). The first line outputs the random seed corresponding to this test point (be careful not to swap the order of filenames and seeds). The second line lists the operations in order (up, down, left, right are represented by uppercase letters `UDLR`).

### Sample Explanation The sample above is a legal output for `20481.out`. It may not be able to achieve the full score for this test point. Each test point is scored independently, and all test points have equal weight. If your output is illegal or does not meet the requirements, the score is $0$; otherwise, you get the full score for that test point. The requirements are as follows. For test points $1-2$: your final state contains a tile with label at least $4096$. For test points $3-5$: your final state contains a tile with label at least $8192$. For test points $6-10$: your final state contains a tile with label at least $16384$. For test points $11-20$: your final state contains a tile with label at least $32768$. Translated by ChatGPT 5