Multi-Problem Contest: Square Sum, Sequence Evaluation, Maximum Rainfall, Maze and RSA Decryption

This contest consists of 5 independent tasks. Participants are required to submit a single output – a result‐fill answer – which is computed by a program without any external input. The 5 tasks are described below:

Problem A: Square Sum

Consider all positive integers in the range \(1\) to \(2019\) that have at least one digit equal to \(2\), \(0\), \(1\) or \(9\) in their decimal representation. For example, in the range \(1\) to \(40\), the numbers satisfying the condition are \(1, 2, 9, 10,\dots, 32, 39, 40\) with a total count of 28. Let the square sum be the sum of the squares of these numbers. Compute the square sum for all numbers in \(1\) to \(2019\).

Problem B: Sequence Evaluation

Consider the sequence defined as \(a_1 = a_2 = a_3 = 1\) and for \(n \ge 4\), \(a_n = a_{n-1} + a_{n-2} + a_{n-3}\). Determine the last 4 digits (in decimal) of \(a_{20190324}\). It is guaranteed that the thousand digit is non-zero.

Problem C: Maximum Rainfall

A magician in a drought‐stricken kingdom possesses 49 magic talismans numbered from 1 to 49. He will cast a spell over 7 weeks by using 7 distinct talismans per week. In each week, the spell energy is calculated as the median (the 4th smallest number) among the week’s 7 numbers. After 7 weeks the rainfall obtained is equal to the median of these 7 weekly energies. By choosing an optimal arrangement of the talismans, what is the maximum possible rainfall (an integer)?

Problem D: Maze

The maze is given as a grid where 0 represents an open cell and 1 an obstacle. Movement is allowed only in the four cardinal directions (up, down, left, right). The entrance is at the upper‐left cell and the exit at the lower‐right cell. Among all shortest paths, find the one with the smallest lexicographic order with the letter ordering defined as: \(D < L < R < U\) (i.e. letter D is considered smallest). In the description, an example small maze is given but the actual challenge is based on a 30×50 maze provided in the statement.

Problem E: RSA Decryption

RSA is a classic encryption algorithm. Its encryption procedure is as follows. Two prime numbers \(p\) and \(q\) are chosen and \(n = p \cdot q\). Given an integer \(d\) that is coprime to \((p-1)(q-1)\), there exists an \(e\) such that \[ d \cdot e \equiv 1 \pmod{(p-1)(q-1)} \] The public key is \((n, d)\) and the private key is \((n, d, e)\). To encrypt a message \(X (< n)\), compute \(C = X^d \bmod n\). To decrypt \(C\), compute \(X = C^e \bmod n\).

You are given a public key with \(n = 1001733993063167141\) and \(d = 212353\), and a captured ciphertext \(C = 20190324\). Determine the original message \(X\) (an integer).

Answer Submission: Each problem is result-fill. You only need to compute the result and print that value without any extra formatting or text.

inputFormat

No input is provided. Your program should directly compute and output the final answers.

outputFormat

Your program should output exactly 5 lines. The first line is the answer to Problem A, the second line is for Problem B, the third line for Problem C, the fourth line for Problem D, and the fifth line for Problem E.

sample

2658417853
8064
30
DRRURRDDDR
20181234

</p>