P3798 Kaguya-hime's Ten Challenges

Meihong recently started playing a small game called $2048$.  (The picture shows a personal best with no undo — hand played.).

$2048$ is a very simple number game played on a $4 \times 4$ board. By moving to merge numbers, reaching $2048$ counts as a win. Meihong has become addicted to the game. When the news reached Kaguya, she decided to test Meihong with ten puzzles that no one had solved before. Game rules: 1. The game is played on an $n \times m$ grid. 2. There are two players. One can move the numbers on the board, denoted by M, and the other can place numbers on the board, denoted by C. 3. The rules for moving numbers are as follows: you can move in one of the four directions: up/down/left/right. After choosing a direction, all numbers slide toward that direction. When two equal numbers collide, they merge into a new number equal to their sum. In a single move, each tile can merge at most once, and merges prioritize tiles closer to the edge in the movement direction. For example, when $n=2, m=4$ ($0$ denotes an empty cell): ``` 2 2 2 2 2 2 0 2 ``` After moving left, it becomes: ``` 4 4 0 0 4 2 0 0 ``` After each merge, you gain score equal to the sum of all newly created numbers from merges in that move. If no merges occur, you gain no score. In the example above, the score is $12$. If, before and after a move, all numbers on the board have the same values and positions, the move is not valid; otherwise, it is a valid move. 4. The rules for placing numbers are as follows: you may place a number only in an empty cell, and which numbers can be placed and how they are placed are specified in each subtask. 5. The game starts with an empty board and a score of $0$. Player C takes two moves first. Then players M and C alternate moves, and every move in between must be valid. When it is player M’s turn and they cannot make a valid move, the game ends, and the current score is the final score. This is an output-only problem with $10$ subtasks for you to complete. Write your answers to $10$ files named ```gamex.out```, where $x$ is the subtask index ($0 \ldots 9$). There are no partial points within a subtask; you receive the subtask’s score if and only if your output exactly matches the reference answer. The ten challenges are as follows: 0. $n=1, m=2$. When player C acts, they may place $2$ or $4$. Let $x$ denote the maximum number of moves player M can make in a single game. What are the extremal values of $x$? Output two lines: the first line is an integer for the minimum possible $x$, and the second line is an integer for the maximum possible $x$. 1. $n=10738029, m=921023$. When player C acts, they may place $2$ or $4$. Let $x$ be the sum of all numbers on the board. What is the maximum value of $x$? Because this value may be too large, output it modulo $10^9+7$. 2. $n=2, m=2$. When player C acts, they may place $2, 4$. Let $x$ denote the target number, where $x$ is a positive power of $2$. Player M’s goal is to make a number at least $x$ appear on the board, while player C’s goal is to end the game before a number $x$ appears on the board. Under optimal play by both sides, find the largest $x$ such that player M can achieve their goal. 3. $n=4, m=4$. When player C acts, they may place $2, 4$. Output two lines, each with one number. The first line is the maximum achievable score. The second line is the minimum score when the total sum of numbers on the board reaches its maximum. 4. $n=7393, m=9133$. Player C can place the number $2$ a total of $6144$ times. The board is initially empty and the initial score is $0$. First, player C acts consecutively until they use all placement opportunities or voluntarily stop early. Then move upward repeatedly until an upward move is no longer valid. Output one integer on a single line: the maximum score. 5. $n=7, m=233$. The initial score is $0$. Player C can place the number $2$ a total of $233$ times and the number $4$ a total of $66$ times. The first row initially contains some numbers: the number in column $i$ is $\text{lowbit}(i) \times 2$, where $\text{lowbit}(i)$ denotes the number formed by taking only the last $1$ in the binary representation of $i$. For example, $\text{lowbit}(1 \ldots 8)$ are $1, 2, 1, 4, 1, 2, 1, 8$. All other cells are empty. First, player C acts consecutively until they use all placement opportunities or voluntarily stop early. Then move upward repeatedly until an upward move is no longer valid. Output one integer on a single line: the maximum score. 6. $n=3, m=3$. When player C acts, they may place $2, 4$. Let $x$ denote the target number, where $x$ is a positive power of $2$. Player M’s goal is to make a number $x$ appear on the board, while player C’s goal is to end the game before a number $x$ appears. Under optimal play by both sides, output the largest $x$ such that player M can achieve their goal. 7. $n=3, m=3$. When player C acts, they may place $2, 4$. Player M’s goal is to maximize the score, and player C’s goal is to minimize the score. Under optimal play by both sides, output an integer representing the final score. 8. $n=3, m=3$. When player C acts, there is a $90\%$ chance to place a $2$ and a $10\%$ chance to place a $4$, with equal probability among all empty cells. Let $x$ denote the target number. Player M’s goal is to make a number at least $x$ appear on the board. Under player M’s optimal strategy, output one line with $9$ real numbers, rounded to $2$ decimal places and separated by spaces, representing the probability of achieving the target for $x=2, 4, 8, 16, 32, 64, 128, 256, 512$. 9. $n=3, m=3$. When player C acts, there is a $90\%$ chance to place a $2$ and a $10\%$ chance to place a $4$, with equal probability among all empty cells. Player M’s goal is to maximize the score. Under player M’s optimal strategy, output one real number, rounded to the nearest integer, representing the expected score. Although Meihong has some understanding of $2048$, she cannot solve all the problems, so she turns to you, who studies OI.

See the problem statement.

See the problem statement.

If you are unsure about the movement rules, you can try them on the $2048$ website: http://gabrielecirulli.github.io/2048/ by-orangebird. Translated by ChatGPT 5