Problem Description

Task A: Number of Composite Numbers

Problem Description

A number is called a composite number if it has divisors other than $1$ and itself. For example, $1,2,3$ are not composite numbers, while $4,6$ are composite numbers.

How many composite numbers are there from $1$ to $2020$?

Answer Submission

This is a fill-in-the-blank question. You only need to compute the result and submit it. The result is an integer. When submitting, only fill in this integer; any extra content will cause you to receive no score.

Task B: Days Containing $2$

Problem Description

Xiao Lan especially likes $2$. This year is AD $2020$, so he is very happy because he can see $2$ on the calendar every day.

If the calendar displays only year, month, and day, from AD $1900$ year $1$ month $1$ day to AD $9999$ year $12$ month $31$ day, how many days have a date that contains $2$ on the calendar? That is, on how many days does the digit $2$ appear in the digits of the year, month, or day?

Answer Submission

This is a fill-in-the-blank question. You only need to compute the result and submit it. The result is an integer. When submitting, only fill in this integer; any extra content will cause you to receive no score.

Task C: Essentially Increasing Subsequences

Problem Description

Xiao Lan especially likes monotonically increasing things.

In a string, if you pick some characters and keep their relative order as in the original string, and the resulting sequence is strictly increasing, then it is called a strictly increasing subsequence of this string.

For example, in the string lanqiao, if you take the characters $\mathrm{n}$ and $\mathrm{q}$, then $\mathrm{nq}$ forms a strictly increasing subsequence. Other such subsequences include Inq, i, ano, and so on.

Xiao Lan found that some subsequences have different positions but the same character sequence. For example, taking the second character and the last character yields $\mathrm{ao}$, and taking the last two characters also yields ao. Xiao Lan thinks they are not essentially different.

For a string, Xiao Lan wants to know how many essentially different increasing subsequences it has.

For example, for the string lanqiao, there are $21$ essentially different increasing subsequences. They are l, a, n, q, i, o, ln, an, lq, aq, nq, ai, lo, ao, no, io, lnq, anq.

For the following string (a total of $200$ lowercase English letters, shown in four lines): (If you copy the following text into a text file, please be sure to check that the copied content is exactly the same as in the document. There is a file inc.txt in the task directory, whose content is the same as the text below.)

tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhewl

How many essentially different increasing subsequences are there?

Answer Submission

This is a fill-in-the-blank question. You only need to compute the result and submit it. The result is an integer. When submitting, only fill in this integer; any extra content will cause you to receive no score.

Task D: So Near Yet So Far

Problem Description

A Peano curve is a curve on the plane.

The figure below shows the order-$1$ Peano curve. It starts from the lower-left corner, passes through every cell in a $3 \times 3$ grid, and finally reaches the upper-right corner.

Assume each cell has side length $1$. In the figure above, some adjacent cells (4-neighbor adjacency) are also adjacent on the Peano curve, so their distance along the curve is $1$. Some adjacent cells are not adjacent on the curve, so their distance along the curve is greater than $1$.

For example, the cells above and below the center cell are adjacent to it on the Peano curve, so the distance is $1$, while the left and right cells are not adjacent to it on the curve, so the distance is $3$.

The figure below shows the order-$2$ Peano curve. It passes through every cell in a $3^{2} \times 3^{2}$ grid. It is obtained by replacing each cell of the order-$1$ curve with an order-$1$ curve.

The figure below shows the order-$3$ Peano curve. It passes through every cell in a $3^{3} \times 3^{3}$ grid. It is obtained by replacing each cell of the order-$2$ curve with an order-$1$ curve.

A Peano curve always starts from the lower-left corner and finally reaches the upper-right corner.

Xiao Lan is curious about the adjacency relationship of neighboring cells on the Peano curve. He wants to know the sum of distances along the curve for all pairs of adjacent cells.

For example, for the order-$1$ Peano curve, the distance sum is $24$: there are $8$ pairs of adjacent cells with distance $1$, $2$ pairs with distance $3$, and $2$ pairs with distance $5$.

For another example, for the order-$2$ Peano curve, the distance sum is $816$.

Please compute the distance sum for the order-$12$ Peano curve.

Hint: The answer does not exceed $10^{18}$.

Answer Submission

This is a fill-in-the-blank question. You only need to compute the result and submit it. The result is an integer. When submitting, only fill in this integer; any extra content will cause you to receive no score.

Task E: Toy Snake

Problem Description

Xiao Lan has a toy snake with a total of $16$ segments, labeled with numbers $1$ to $16$. Each segment is a square. Two adjacent segments can be in a straight line or form a $90$ degree angle.

Xiao Lan also has a $4 \times 4$ grid box to store the toy snake. The cells of the box are labeled with the letters $\mathrm{A}$ to $\mathrm{P}$, a total of $16$ letters.

Xiao Lan can fold the toy snake and place it into the box. He found that there are many ways to put the toy snake in.

The figure below shows two ways:

Please help Xiao Lan compute how many different ways there are in total. If in two ways, there exists some segment of the toy snake that is placed in a different cell of the box, then the two ways are considered different.

Answer Submission

This is a fill-in-the-blank question. You only need to compute the result and submit it. The result is an integer. When submitting, only fill in this integer; any extra content will cause you to receive no score.

Input Format

Input a capital letter, indicating which task it is.

Output Format

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

Hint

Answer template for reference.

#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "The answer of task A", // Replace the content in double quotes with the answer for Task A
        "The answer of task B", // Replace the content in double quotes with the answer for Task B
        "The answer of task C", // Replace the content in double quotes with the answer for Task C
        "The answer of task D", // Replace the content in double quotes with the answer for Task D
        "The answer of task E", // Replace the content in double quotes with the answer for Task E
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}

Translated by ChatGPT 5