Problem Description

A Sum of Squares

Problem Description

Xiaoming is very interested in numbers whose digits contain 2, 0, 1, or 9. From $1$ to $40$, such numbers include $1$, $2$, $9$, $10$ to $32$, $39$, and $40$, totaling $28$ numbers. Their sum is $574$, and the sum of squares is $14362$. Note that the sum of squares means squaring each number and then summing them up.

In $1$ to $2019$, what is the sum of squares of all such numbers?

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 result in no score.

Hint: If you write a program to compute it and find that the result is negative, please carefully check your program. Do not doubt the programming software used in the contest.

B Sequence Evaluation

Problem Description

Given the sequence $1,1,1,3,5,9,17,\cdots$, starting from the $4$-th term, each term equals the sum of the previous $3$ terms. Find the last $4$ digits of the $20190324$-th term.

Answer Submission

This is a fill-in-the-blank question. You only need to compute the result and submit it. The result is a $4$-digit integer (hint: the thousands digit is not $0$). When submitting, only fill in this integer; any extra content will result in no score.

C Maximum Rainfall

Problem Description

Because the Land of Sand has been dry for many years, the mage Xiaoming plans to cast a mysterious spell to make it rain.

This spell requires the $49$ spell cards in his hand, each labeled with a number from $1$ to $49$. The spell lasts for $7$ weeks. Every day, Xiaoming must use one spell card, and no card may be used more than once.

Each week, the energy produced by the spell is the median of the numbers on the $7$ spell cards used that week. After $7$ weeks, the rainmaking will succeed, and the rainfall is the median of the energies of the $7$ weeks.

Since it has been dry for too long, Xiaoming wants the rainfall to be as large as possible. What is the maximum value?

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 result in no score.

D Maze

Problem Description

The following figure gives a top view of a maze. Cells marked as $1$ are obstacles, and cells marked as $0$ are passable.

010000
000100
001001
110000

The entrance of the maze is the top-left corner, and the exit is the bottom-right corner. In the maze, you can move from one cell to one of its four directions: up, down, left, or right.

For the maze above, starting from the entrance, you can pass through the maze by following DRRURRDDDR, for a total of $10$ steps. Here D, U, L, R represent moving down, up, left, and right, respectively.

For the more complex maze below ($30$ rows and $50$ columns), please find a way to pass through the maze using the minimum number of steps. Among all shortest paths, output the one with the smallest lexicographical order. Note that in lexicographical order, $\mathrm{D}<\mathrm{L}<\mathrm{R}<\mathrm{U}$. (If you copy the following text into a file, be sure to check that the copied content is exactly the same as in the document.)

01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

Answer Submission

This is a fill-in-the-blank question. You only need to compute the result and submit it. The result is a string containing the four letters D, U, L, R. When submitting, only fill in this string; any extra content will result in no score.

E RSA Decryption

Problem Description

$\mathrm{RSA}$ is a classic encryption algorithm. Its basic encryption process is as follows.

First generate two prime numbers $p, q$. Let $n=p \cdot q$. Let $d$ be coprime to $(p-1) \cdot(q-1)$. Then we can find $e$ such that the remainder of $d \cdot e$ divided by $(p-1) \cdot(q-1)$ is $1$.

$n, d, e$ form the private key, and $n, d$ form the public key.

When using the public key to encrypt an integer $X$ (less than $n$), compute $C=X^{d} \bmod n$, and $C$ is the encrypted ciphertext.

When receiving the ciphertext $C$, we can decrypt it using the private key by computing $X=C^{e} \bmod n$.

For example, when $p=5, q=11, d=3$, we have $n=55, e=27$.

If we encrypt the number $24$, we get $24^{3} \bmod 55=19$.

If we decrypt the number $19$, we get $19^{27} \bmod 55=24$.

Now you know that in the public key $n=1001733993063167141, d=212353$, and you have intercepted a ciphertext $C=20190324$ sent by someone else. What is the plaintext?

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 result in no score.

Input Format

Input one uppercase letter indicating which problem it is.

Output Format

According to the input problem label, output the corresponding answer.

Hint

Answer template for reference.

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

Translated by ChatGPT 5