| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14090 | Domo's Treasure Hunt |
|
| 14093 | Sorting ㄇㄧㄥˊ ㄗˋ |
|
Description
Domo is a brilliant dog.
Today he comes out for a jog.
Domo likes walking in cities,
because he can earn some money.
The town map is M columns, N rows.
The dog departs from (0, 0)
He will collect money in town,
but he only goes right or down.
There'll be an int within each cell.
How much money: the number tells.
For every cell Domo visit,
he'll take the money as the "profit."
Domo's goal is the low-right corner.
He wants money greatest in number.
Please help Domo to inspect.
How much money can he collect?
Input
The first line consists of two positive integers M and N. (1 ≤ M, N ≤ 1024).
The next N lines, containing M integers each, represent the money in each cell. For all cells, the number of money aij, 0 ≤ aij ≤ 108.
Output
The maximum amount of money Domo can get from the city, followed by an end-line character.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Learning Chinese characters is not an easy task. The list of characters in common use by the Ministry of Education alone contains 4808 characters, not to mention the even rarer ones in the Kangxi Dictionary. Even native speakers might sometimes run into an unknown character. This is why people tried to come up with different ways to represent the sounds of the characters. In modern times, there are two major methods to do this: Zhuyin Fuhao (注音符號) and Hanyu Pinyin (漢語拼音), with the former being widespread among Taiwanese and the latter among foreigners.
Figure 1: Zhuyin Fuhao onsets (聲母) and their Pinyin counterparts. The grayed-out ones are not used in modern Mandarin.
Figure 2: Zhuyin Fuhao finals (韻母) and their Pinyin counterparts.
When Chinese characters are ordered by Zhuyin Fuhao, the onset is to be considered first. The order goes b ㄅ, p ㄆ, m ㄇ, f ㄈ... z ㄗ, c ㄘ, s ㄙ, and, lastly, those without an onset. If the onset is the same, they are ordered by the medial vowel: i ㄧ, u ㄨ, ü ㄩ, and lastly the main vowel and the coda: a ㄚ, o ㄛ, e ㄜ, ê ㄝ, ai ㄞ, ei ㄟ, ao ㄠ, ou ㄡ, an ㄢ, en ㄣ, ang ㄤ, and eng ㄥ.
As for the Pinyin system, each character is transcribed using the Latin alphabet. The rules are:
1. If the onset is present, the syllable is typically formed by combining the onset and the final.
清(ㄑㄧㄥ) is written as qing
2. If the onset is present, and the final is iou, uei, uen, or ueng, the final will be written as -iu, -ui, -un, and -ong respectively.
牛(ㄋㄧㄡˊ) is written as niu rather than *niou
3. If the onset is j ㄐ, q ㄑ, or x ㄒand the final starts with ü, the final will be written with u instead.
學(ㄒㄩㄝˊ) is written as xue rather than *xve or *xüe (Since ü is not an ASCII character, v is often used instead.)
4. When the onset is not present, the letters i and u at the beginning of the final will change to y and w, respectively, unless it is the sole vowel in the final, where the letter would be appended at the beginning.
我(ㄨㄛˇ) is written as wo rather than *uo.
五(ㄨˇ ) is written as wu rather than *u.
5. When the onset is not present, the letters ü at the front of the final will always change to yu.
元(ㄩㄢˊ ) is written as yuan rather than *üan or *van.
6. If the second syllable has no onset nor medial vowel (i.e., it starts with a, o, or e), an apostrophe ' should be used before the syllable if the lack results in ambiguity.
西安(ㄒㄧ ㄢ) is written as xi'an as opposed to 先 (ㄒㄧㄢ) xian.
命案(ㄇㄧㄥˋ ㄢˋ ) is written as ming'an as opposed to 敏感 (ㄇㄧㄣˇ ㄍㄢˇ) mingan
In this task, you must sort the names written in Pinyin based on the Zhuyin order. For example, if the names in the list are:
| Chinese Name | Zhuyin Transcription | Pinyin Romanization |
|---|---|---|
| 胡敏君 | ㄏㄨˊ ㄇㄧㄣˇ ㄐㄩㄣ | Hú Mǐnjūn |
| 景璞 | ㄐㄧㄥˇ ㄆㄨˊ | Jǐng Pú |
| 蕭澤然 | ㄒㄧㄠ ㄗㄜˊ ㄖㄢˊ | Xiāo Zérán |
| 莊景堯 | ㄓㄨㄤ ㄐㄧㄥˇ ㄧㄠˊ | Zhuāng Jǐngyáo |
| 歐偉興 | ㄡ ㄨㄟˇ ㄒㄧㄥ | Ōu Wěixīng |
| 徐美妮 | ㄒㄩˊ ㄇㄟˇ ㄋㄧˊ | Xú Měiní |
| 曾恩傑 | ㄗㄥ ㄣ ㄐㄧㄝˊ | Zēng Ēnjié |
| 高敦晉 | ㄍㄠ ㄉㄨㄣ ㄐㄧㄣˋ | Gāo Dūnjìn |
| 許木羽 | ㄒㄩˇ ㄇㄨˋ ㄩˇ | Xǔ Mùyǔ |
| 鄭敦謙 | ㄓㄥˋ ㄉㄨㄣ ㄑㄧㄢ | Zhèng Dūnqiān |
The output will be ordered as:
| Chinese Name | Zhuyin Transcription | Pinyin Romanization |
|---|---|---|
| 高敦晉 | ㄍㄠ ㄉㄨㄣ ㄐㄧㄣˋ | Gāo Dūnjìn |
| 胡敏君 | ㄏㄨˊ ㄇㄧㄣˇ ㄐㄩㄣ | Hú Mǐnjūn |
| 景璞 | ㄐㄧㄥˇ ㄆㄨˊ | Jǐng Pú |
| 蕭澤然 | ㄒㄧㄠ ㄗㄜˊ ㄖㄢˊ | Xiāo Zérán |
| 徐美妮 | ㄒㄩˊ ㄇㄟˇ ㄋㄧˊ | Xú Měiní |
| 許木羽 | ㄒㄩˇ ㄇㄨˋ ㄩˇ | Xǔ Mùyǔ |
| 鄭敦謙 | ㄓㄥˋ ㄉㄨㄣ ㄑㄧㄢ | Zhèng Dūnqiān |
| 莊景堯 | ㄓㄨㄤ ㄐㄧㄥˇ ㄧㄠˊ | Zhuāng Jǐngyáo |
| 曾恩傑 | ㄗㄥ ㄣ ㄐㄧㄝˊ | Zēng Ēnjié |
| 歐偉興 | ㄡ ㄨㄟˇ ㄒㄧㄥ | Ōu Wěixīng |
Don't worry: you aren't going to write the comparing function and the whole sorting algorithm yourself. You only have to implement two functions, one to swap two strings and one to partition the string between the index l and r (inclusively), as well as return the index of the partition pivot. You are given a comparing function int compareByZhuyin(const char* str1, const char* str) which returns a negative value when str1 should come before str2, a positive value when str2 should come before str1, and zero when both strings are equal.
Input
The first line contains an integer N, specifying how many names are in the list.
The next N lines are the names that you want to sort, written in Pinyin system with tones omitted.
Output
The sorted list of name, based on Zhuyin order.