2048 Puzzle Challenges

This problem is inspired by the famous game $2048$. In this game, an $n \times m$ board is used and two players take turns with different roles:

• Player M can move the numbers on the board in one of four directions (up, down, left, right). When moved, all numbers slide as far as possible toward the selected direction. If two identical numbers collide, they merge to form a new number equal to the sum of the colliding numbers. In a single move each number can merge at most once, and merges occur sequentially from the side toward which the board is moving. Merging gives a score equal to the sum of the newly formed numbers. A move is considered valid if the board, in terms of both number values and positions, changes after the move.
• Player C places new numbers onto empty cells. The choices of numbers and the placement rules depend on the subtask.

The game begins with an empty board and score $0$. Player C makes the first two moves consecutively, and thereafter the players alternate moves. Every move must be valid. When it is Player M's turn and no valid move exists, the game ends and the current score is the final score.

This challenge consists of 10 subtasks (numbered from 0 to 9), each with different board sizes, placement rules, and goals. For example:

1. Subtask 0: $n=1, m=2$. Player C may place a $2$ or a $4$. Let $x$ be the maximum number of moves Player M can make in one game. Output two lines: the first line is the minimum possible $x$ and the second line is the maximum possible $x$.
2. Subtask 1: $n=10738029, m=921023$. With the same placement rules, let $x$ be the sum of all numbers on the board. Output $x \bmod (10^9+7)$.
3. ... and so on until subtask 9.

Note: In this "output-answer" problem you must output exactly the expected answer for each subtask. Your solution is required to write the answer to 10 files, named game0.out, game1.out, ..., game9.out. For our purposes the program will be given an input indicating the subtask number (an integer between 0 and 9), and your program should output the corresponding answer exactly.

All formulas in this statement are in \(\LaTeX\) format.

inputFormat

The input consists of a single integer s on the first line (where 0 ≤ s ≤ 9), which indicates the subtask number. Based on s, your program should output the exact answer for that subtask.

outputFormat

Output exactly the answer corresponding to the given subtask number s:

• Subtask 0: Output two lines. The first line is the minimum number of moves and the second line is the maximum number of moves that Player M can make.
• Subtask 1: Output one integer which is the maximum sum of all numbers on the board modulo \(10^9+7\).
• Subtask 2: Output one integer representing the largest target power of 2 that Player M can achieve.
• Subtask 3: Output two lines. The first line represents the maximum score possible, and the second line represents the minimum score among those maximum total numbers.
• Subtask 4: Output one integer indicating the maximum score obtained by continuously placing a 2 by Player C then moving up repeatedly.
• Subtask 5: Output one integer indicating the maximum score under the given conditions with pre-filled first row.
• Subtask 6: Output one integer which is the largest target power of 2 that Player M can achieve under optimal play.
• Subtask 7: Output one integer representing the final score under optimal play where Player M maximizes and Player C minimizes the score.
• Subtask 8: Output one line with 9 real numbers (rounded to 2 decimal places) separated by a single space. Each number represents the probability of achieving a target number when x is set to \(2,4,8,16,32,64,128,256,512\), respectively.
• Subtask 9: Output one integer representing the expected score (rounded to the nearest integer) under optimal play for Player M.

sample

0

1
100