P8689 [Lanqiao Cup 2019 National A] Fill-in-the-Blank Problems

## Task A: Triple Increasing Sequences ### Problem Description For a letter matrix, we define a “triple increasing sequence” as follows: find three letters in the matrix that lie in the same row, the same column, or on the same $45$-degree diagonal line, and these three letters are in increasing order when read from left to right, from right to left, or from top to bottom. For example, in the following matrix: ```plaintext YQPD BKEZ AFYV ``` there are `BKZ`, `BEZ`, `AFY`, `AFV`, `AKP`, `DEF`, etc., a total of $6$ triple increasing sequences. Note that when the three letters are arranged from bottom-left to top-right, reading from left to right and reading from top to bottom give different orders. For the following $30$-row $50$-column matrix, how many triple increasing sequences are there in total? (If you copy the text below into a file, be sure to check that the copied content matches the document. There is an attached file inc.txt whose content is the same as the text below.) ```plaintext VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX ``` ### Answer Submission This is a fill-in-the-blank problem. You only need to compute the result and submit it. The result is an integer. When submitting, fill in only this integer; any extra content will not be graded. ## Task B: Optimal Travel ### Problem Description China’s high-speed rail network extends in all directions and is convenient to take. Xiaoming often travels between cities by high-speed rail. Now Xiaoming has another long holiday, and he plans to continue traveling by high-speed rail. This time, he plans to visit the following cities: Shanghai, Guangzhou, Changsha, Xi’an, Hangzhou, Jinan, Chengdu, Nanjing, Kunming, Zhengzhou, Tianjin, Taiyuan, Wuhan, Chongqing, Nanchang, Changchun, Shenyang, Guiyang, Fuzhou. Xiaoming plans to depart from Beijing, visit each of the above cities exactly once, and finally return to Beijing. In each city (except Beijing), Xiaoming must stay for at least 24 hours. And when Xiaoming decides to travel from one city to another, he will only choose cities with a direct high-speed rail connection, and will not transfer midway. There is an attached file trip.txt that stores the train services Xiaoming can choose. Xiaoming will not choose any other services. Xiaoming departs at 12:00 noon on day $1$. Ask: if Xiaoming visits each of the above cities exactly once and finally returns to Beijing, what is the minimum number of minutes required? (Note the unit is minutes. Also note that except for Beijing, each city requires at least $24$ hours of stay, i.e. at least $1440$ minutes.) ### Answer Submission This is a fill-in-the-blank problem. You only need to compute the result and submit it. The result is an integer. When submitting, fill in only this integer; any extra content will not be graded. ## Task $\mathrm{C}$: Dice Manufacturing ### Problem Description Dice are a commonly used tool in games. A die is a regular cube, with the six faces showing $1$ to $6$ pips, one of each. Usually, the appearances of pips $1$ to $6$ are as shown in the figure below.  Among them, the shapes of $1$, $4$, and $5$ remain unchanged after rotations of $90$, $180$, or $270$ degrees, while the shapes of $2$, $3$, and $6$ remain unchanged after a rotation of $180$ degrees. Xiaoming wants to manufacture a batch of dice, and he hopes to make them more interesting. He wants any two of the dice he makes to be different under any rotation. What is the maximum number of dice he can make? ### Answer Submission This is a fill-in-the-blank problem. You only need to compute the result and submit it. The result is an integer. When submitting, fill in only this integer; any extra content will not be graded. ## Task D: Sequence Summation ### Problem Description After learning about divisors, Xiaoming became very curious about them. He found that, given a positive integer $t$, it is always possible to find an integer that has exactly $t$ divisors. Xiaoming is very interested in the smallest number that has $t$ divisors, and he defines it as $S_{t}$. For example, $S_{1}=1，S_{2}=2，S_{3}=4，S_{4}=6，\cdots$. Now Xiaoming wants to know the sum of the first $60$ values of $S_{i}$. That is, what is $S_{1}+S_{2}+\cdots+S_{60}$? ### Answer Submission This is a fill-in-the-blank problem. You only need to compute the result and submit it. The result is an integer. When submitting, fill in only this integer; any extra content will not be graded. ## Task E: Square-Free Set ### Problem Description Xiaoming does not really like perfect squares. He even does not like two numbers whose sum is a perfect square. Today, he wants to choose some numbers from $1$ to $100$ to form a set, with the requirements that he does not choose any perfect square, and the sum of any two numbers in the set cannot be a perfect square either. What is the maximum number of elements Xiaoming can choose? ### Answer Submission This is a fill-in-the-blank problem. You only need to compute the result and submit it. The result is an integer. When submitting, fill in only this integer; any extra content will not be graded.

Input one uppercase letter, indicating which task it is.

According to the input task letter, output the answer for the corresponding task.

Answer template for reference. ```cpp #include using namespace std; int main() { string ans [] = { "The answer of task A", // Replace the content in double quotes with the answer for task A "The answer of task B", // Replace the content in double quotes with the answer for task B "The answer of task C", // Replace the content in double quotes with the answer for task C "The answer of task D", // Replace the content in double quotes with the answer for task D "The answer of task E", // Replace the content in double quotes with the answer for task E }; char T; cin >> T; cout