ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - c132: 00619 - Numerically Speaking 解題心得

Not In My Back Yard | 2019-02-14 23:45:32 | 巴幣 0 | 人氣 204

題目連結:


題目大意:
令:
a = 1
b = 2
……
z = 26
aa = 27
ab = 28
……
snowfall = 157, 118, 051, 752
……

題目有多筆測試資料,每筆測試資料一列。每一列有一字串,可能是只由小寫字母組成(長度最多 20 個字母),或是純數字組成的。給定字母字串的話,將其按照上面的規律轉成數字;給定純數字字串的話,則傳成字母。

輸出時,字母字串跟純數字字串都要輸出於一列。且先輸出字母字串,再從每列第 23 個字母開始輸出純數字字串,並從右邊算起每3位以「,」隔開。參見範例輸出。

當給定的字串為「*」時,代表輸入結束。請停止程式。



範例輸入:
29697684282993
transcendental
28011622636823854456520
computationally
zzzzzzzzzzzzzzzzzzzz
z
*


範例輸出:
elementary            29,697,684,282,993
transcendental        51,346,529,199,396,181,750
prestidigitation      28,011,622,636,823,854,456,520
computationally       232,049,592,627,851,629,097
zzzzzzzzzzzzzzzzzzzz  20,725,274,851,017,785,518,433,805,270
z                     26


解題思維:
可以看到題目給定的規律實為 26 進位。像是常用的 10 進位和 2 進位,這邊的 26 進位即是採用 a ~ z 作為位數的符號。而例如像是 abd 代表的是:
(1 × 26 ^ 2) + (2 × 26 ^ 1) + (4 × 26 ^ 0) = 732
而因為字串長度可到 20 個字母長,因此需要大數乘法、加法。參見這裡

而如果是純數字轉成字母,以剛剛的 732 為例:
732 ÷ 26 = 28 …… 餘 4 → d
28 ÷ 26 = 1 …… 餘 2 → b
1 ÷ 26 = 0 …… 餘 1 → a
因此,732對應到的字母字串即是 abd 。由上可以看到,只要一直除以 26 ,並取餘數再傳成相應的字母,除到商數為 0 為止。

輸出的話,C++ 可以使用 setw() 函式來設定輸出的間距。 setw(22) 即代表接下來的輸出不長度多長,都要佔 22 個字元長,不夠的用空白補齊。但是因為預設是靠右對齊(空白會在左邊),所以要用 cout << left 來設定靠左邊。

接著的數字部分可以另外轉成普通的字串,再根據長度以「,」分隔。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

胖胖貓
其實這題的轉換數字範圍剛好落在 __int128 以內,可以不用辛苦的轉乘大數處理
撇開大數部分格式也很麻煩就是...
2019-02-15 03:13:40
Not In My Back Yard
__int128 似乎不是每個編譯器都支援(不是 C++/C 的標準),所以我通常不用XD

不過說到格式,畢竟原題是 UVa 的題目,會麻煩是正常的。UVa 的題目有時候輸出格式反而比題目難。
像是 Q11113 - Continuous Fractions 這題的格式也很開心 :)
2019-02-15 11:04:01

相關創作

更多創作