P8750 [Lanqiao Cup 2021 NOI Qualifier A2] Fill-in-the-Blank Problems

## Task A: Double Factorial ### Problem Description The double factorial of a positive integer is defined as the product of all positive integers not exceeding it and having the same parity as it. The double factorial of $n$ is denoted by $n!!$. For example: $3!!=3 \times 1=3$. $8!!=8 \times 6 \times 4 \times 2=384$. $11!!=11 \times 9 \times 7 \times 5 \times 3 \times 1=10395$. What are the last $5$ digits (in decimal) of $2021!!$? Note: $2021!!=2021 \times 2019 \times \cdots \times 5 \times 3 \times 1$. Hint: It is recommended to solve this problem using computer programming. ### Answer Submission This is a fill-in-the-blank problem. You only need to compute the result and submit it. The result is an integer. When submitting, enter only this integer; any extra content will not be scored. ## Task B: Lattice Points ### Problem Description If a point $(x,y)$ has both coordinates as integers, i.e. $x \in \mathbb{Z}$ and $y \in \mathbb{Z}$, then it is called a lattice point. If a point $(x,y)$ has both coordinates positive, i.e. $x>0$ and $y>0$, then it lies in the first quadrant. Among the lattice points in the first quadrant, how many points $(x,y)$ satisfy that the product of the two coordinates is at most $2021$, i.e. $x \cdot y \leq 2021$? Hint: It is recommended to solve this problem using computer programming. ### Answer Submission This is a fill-in-the-blank problem. You only need to compute the result and submit it. The result is an integer. When submitting, enter only this integer; any extra content will not be scored. ## Task C: Integer Partition ### Problem Description Decomposing $3$ into the sum of two positive integers has two methods: $3=1+2$ and $3=2+1$. Note that different orders count as different methods. Decomposing $5$ into the sum of three positive integers has $6$ methods: $1+1+3=1+2+2=$ $1+3+1=2+1+2=2+2+1=3+1+1$. What is the number of methods to decompose $2021$ into the sum of five positive integers? ### Answer Submission This is a fill-in-the-blank problem. You only need to compute the result and submit it. The result is an integer. When submitting, enter only this integer; any extra content will not be scored. ## Task D: City-States ### Problem Description Xiaolan Kingdom is a water kingdom with $2021$ city-states, numbered from $1$ to $2021$ in order. Between any two city-states, there is a bridge directly connecting them. To celebrate a traditional festival, the government of Xiaolan Kingdom plans to decorate some of the bridges. For two city-states numbered $a$ and $b$, the cost to decorate the bridge between them is calculated as follows: find all digit positions (in base 10) where $a$ and $b$ have different digits, and sum the digits on those positions (from both numbers). For example, between city-states numbered $2021$ and $922$, the thousands, hundreds, and ones digits are all different. Adding the digits on these positions gives $(2+0+1)+(0+9+2)=14$. Note that $922$ has no thousands digit; treat the thousands digit as $0$. To save costs, the government plans to decorate only $2020$ bridges, and it must be guaranteed that from any city-state to any other city-state, one can travel using only decorated bridges. What is the minimum total cost the government must spend to finish the decoration? Hint: It is recommended to solve this problem using computer programming. ### Answer Submission This is a fill-in-the-blank problem. You only need to compute the result and submit it. The result is an integer. When submitting, enter only this integer; any extra content will not be scored. ## Task E: Game ### Problem Description Xiaolan is bored and starts playing a game by himself. First, a positive integer $n$ is given. He first writes down a number between $1$ and $n$ on paper. In each subsequent step, Xiaolan may choose a divisor of the last written number (but cannot choose a number that has already been written before) and write it down. This continues until Xiaolan finally writes down $1$. Xiaolan may have multiple possible plans for the game. For example, when $n=6$, Xiaolan has $9$ plans: $(1)$, $(2,1),(3,1),(4,1),(4,2,1),(5,1)$, $(6,1),(6,2,1),(6,3,1)$. When $n=20210509$, how many plans are there? ### Answer Submission This is a fill-in-the-blank problem. You only need to compute the result and submit it. The result is an integer. When submitting, enter only this integer; any extra content will not be scored. The answer to this problem is relatively large. If you solve it by programming, please use an appropriate data type.

Input a capital letter indicating which task it is.

According to the input task letter, output the corresponding answer.

Answer template, for reference. ```cpp #include using namespace std; int main() { string ans [] = { "The answer of task A", // Replace inside the quotes with the answer for task A "The answer of task B", // Replace inside the quotes with the answer for task B "The answer of task C", // Replace inside the quotes with the answer for task C "The answer of task D", // Replace inside the quotes with the answer for task D "The answer of task E", // Replace inside the quotes with the answer for task E }; char T; cin >> T; cout