Multi-Part Result-Fill Problem Set

This problem set consists of 5 independent subproblems. Each subproblem is a result‐fill question; you are required to output exactly one integer for each subproblem in the order given below, with each answer printed on a separate line.

Problem A: Composite Count

• A number is called composite if it has at least one divisor other than 1 and itself. For example, 4 and 6 are composite while 1, 2, 3 are not.
• Calculate how many composite numbers there are between 1 and 2020 (inclusive).

Problem B: Days Containing Digit 2

• Consider a calendar that shows only the year, month, and day (in the format YYYYMMDD). Count the number of days between January 1, 1900 and December 31, 9999 (inclusive) whose date representation contains the digit 2 at least once.

Problem C: Essentially Distinct Increasing Subsequences

• Given a 200-character lowercase string (provided exactly as below, over 4 lines), a subsequence is obtained by deleting some characters (possibly none) without changing the order. If the letters of the subsequence (in order) form a strictly increasing sequence (in terms of their ASCII codes), then it is a valid increasing subsequence.
• Two subsequences are considered essentially the same if the resulting string is identical, regardless of which positions were chosen.
• Compute the number of essentially different increasing subsequences. For example, for "lanqiao" the answer is 21.
• The 200-character string is given exactly as follows (make sure the file contents match):
  tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhewl

Problem D: Peano Curve Distances

• The Peano curve is a continuous curve that passes through every cell of a 3^n x 3^n grid. For n=1, the curve (shown in the figure) starts at the bottom‑left cell and ends at the top‑right cell of a 3×3 grid. In the curve, some pairs of adjacent grid cells (sharing a side) are adjacent in the curve (distance 1), while others are not (with distances greater than 1).
• For example, for the 1st‑order Peano curve the sum of distances for all pairs of grid‑adjacent cells is 24, and for the 2nd‑order curve it is 816.
• Compute the sum of the distances (along the Peano curve) for all pairs of grid-adjacent cells in the 12th‑order Peano curve. (Hint: the answer does not exceed 10¹⁸.)
• A derived recurrence yields the closed‑form: S(n) = ((200·n – 128)/3) · 9^(n–1). Using n = 12, you are to compute S(12).

Problem E: Toy Snake

• You have a toy snake consisting of 16 segments numbered 1 to 16. Each segment is a square. The segments are connected so that consecutive segments touch along an edge (either in a straight line or at a 90° angle).
• You also have a 4×4 box with its 16 cells labeled A to P. The snake can be folded and placed into the box.
• Count how many distinct ways the snake can be placed into the box. Two placements are considered different if there exists at least one segment that occupies different cells in the two placements.
• This is equivalent to counting the number of Hamiltonian paths on a 4×4 grid (with the snake’s order fixed—in particular, note that a path and its reverse are considered different).
• It turns out that the answer for this problem is 368.

Input/Output: There is no input. Your program should output 5 lines; the first line is the answer for Problem A, the second for Problem B, the third for Problem C, the fourth for Problem D, and the fifth for Problem E.

inputFormat

There is no input.

outputFormat

Output 5 lines. Each line should contain a single integer representing the answer to Problems A, B, C, D, and E respectively.

sample

1713
1685695
67108863
23765922477216
368

</p>