Multi-Task Contest: Five Problems

Problem A: Beautiful \(2\)

Blue really loves the digit 2. In the year 2020, he is particularly excited. He wonders, between the years 1 and 2020 (inclusive), how many years have at least one digit equal to 2 in their decimal representation?

Problem B: Composite Count

A number is called composite if it has a divisor other than 1 and itself. For example, 1, 2, 3 are not composite while 4 and 6 are composite. Count how many composite numbers there are from 1 to 2020 (inclusive).

Problem C: Diffusion

On an infinite grid, each cell is represented by two-dimensional integer coordinates. Initially, only the following cells are black: \( (0,0) \), \( (2020,11) \), \( (11,14) \), and \( (2000,2000) \); all other cells are white. Every minute, black spreads: if a cell is black, its four direct neighbors (up, down, left, right) become black as well. Compute the total number of black cells after 2020 minutes.

Problem D: Divisors of Factorial

Recall that the factorial \(n!\) is defined as \(1 \times 2 \times 3 \times \cdots \times n\). Determine how many positive divisors \(100!\) has.

Problem E: Essentially Increasing Subsequences

Blue loves monotonic increasing sequences. A subsequence of a string (formed by deleting some characters without changing the order) is called increasing if the characters in the subsequence are in strictly increasing order. Note that subsequences that are identical in terms of character sequence are considered the same regardless of which positions are taken. For example, in the string "lanqiao", the increasing subsequences include: l, a, n, q, i, o, ln, an, lq, aq, nq, ai, lo, ao, no, io, lnq, anq, etc. Given an input string (provided as 4 lines containing 200 lowercase English letters in total), determine the number of essentially different increasing subsequences present in the string.

Note for Answer Submission: Each problem requires you to output a single integer as the answer. In the case of problem E, the 4-line input is exactly as provided in the attached file inc.txt.

Input/Output Format: Your program should first read a single line containing a character among {A, B, C, D, E} which indicates the problem to solve. For problem E, the next 4 lines will contain the input string. For the other problems, no further input is provided.

inputFormat

The input begins with a single line containing one uppercase letter among A, B, C, D, E indicating the problem you need to solve.

For Problem E only, the next 4 lines contain a string (each line is part of the 200-character lowercase string). For Problems A, B, C, and D, there is no additional input.

outputFormat

Output a single integer representing the answer for the selected problem.

sample

A

563