Multi-Task Challenge: Frogs, Coprime, License Plates, Fibonacci Set, and Increasing Substrings

Problem Description

This challenge consists of five independent subproblems, labeled A through E. You will be given an input indicator which specifies which subproblem to solve. For subproblems A, B, C, and D no additional input is provided, while subproblem E includes an extra letter matrix input.

Subproblem A: Count Frogs

The following text is written for 1 to 20 frogs. For each integer n (from 1 to 20), a sentence is written in Chinese as follows:

[Chinese(n)]只青蛙[Chinese(n)]张嘴[Chinese(2*n)]只眼睛[Chinese(4*n)]条腿

All punctuation marks are omitted when counting characters. Note that when converting a number to Chinese:

• If the number 2 appears by itself, it is read as “两”.
• In all other cases, the digit 2 is read as “二”.
• For example, 10 is “十”, 11 is “十一”, and 22 is “二十二”.

Calculate the total number of Chinese characters in the fully written description for frogs from 1 to 20. (Answer: 353)

Subproblem B: Coprime Count

Given the year 2020 and the date October 18, 2020, count how many numbers from 1 to 2020 are coprime with 1018. (Answer: 1008)

Subproblem C: License Plates

City A has license plates comprised of six characters. The first three characters can be either digits (0–9) or letters (A–F) (16 possibilities each), and the last three characters can only be digits (0–9). To reduce flaunting, no license plate may contain three consecutive identical characters. For example, "202020" is valid while "AAA202" is not. Determine the number of valid license plates. (Answer: 4002750)

Subproblem D: Fibonacci Set

A set F is defined as follows:

1. The smallest 5 Fibonacci numbers 1, 2, 3, 5, 8 are in F.
2. If an element x is in F, then the numbers 3x+2, 5x+3, and 8x+5 are also in F.
3. No other numbers are in F.

Find the 2020th smallest element in F. (Answer: 26590291)

Subproblem E: Increasing Substrings

You are given a letter matrix. A substring is formed by choosing a starting cell and then moving to adjacent cells (up, down, left, right) where each subsequent letter is strictly greater (in lexicographical order) than the previous one. You may move as many times as you wish and stop at any time. Two substrings are considered different if their sets of positions in the matrix differ. Given the matrix provided in the input, count the total number of increasing substrings. For example, for the matrix:

A B
B C

there are 4 substrings of length 1, 4 of length 2, and 2 of length 3, for a total of 10.

Input/Output Protocol

The input begins with a single character on the first line that indicates the subproblem to solve (A, B, C, D, or E). For subproblems A–D, no additional input is provided. For subproblem E, the following input is given:

• The next line contains two integers m and n, indicating the number of rows and columns.
• This is followed by m lines, each containing a string of n uppercase letters (with no spaces).

The program should output a single integer which is the answer for the chosen subproblem.

inputFormat

The first line contains a single character from {A, B, C, D, E} indicating the subproblem to solve.

If the character is 'E', the second line contains two integers m and n representing the dimensions of the letter matrix. This is followed by m lines, each containing a string of n uppercase letters.

For subproblems A, B, C, and D, there is no additional input.

outputFormat

Output a single integer: the answer for the chosen subproblem.

sample

A

353