切換
舊版
前往
大廳
主題

ZeroJudge - c677: 銀河宮廟 解題心得

Not In My Back Yard | 2018-12-05 15:18:18 | 巴幣 0 | 人氣 169

題目連結:


題目大意:
這題的強化版,現在 N 可以高達 1000000000000000 。


範例輸入:
T 5
T 4
F 10
F 22
T 10000
F 15751
T 1000000000000000



範例輸出:
6
5
9
20
15751
10000
5873731811138871



解題思維:
上一次的做法在這裡是行不通的( N 太大了)。因此我們需要引進一個類似但是稍有不同的想法。

因為不會用到「4」這個數字,就表示 0 ~ 9 只有 9 個數字被用到。而每一位數都是由「4」以外的 9 個數字組成,那不就是「九進位」嗎?

又因為是九進位,我們可以套用我們以前有的經驗去將數字轉換。在做進位制轉換時,要特別跳過「4」。以 0、1、2、3、5、6、7、8、9 作為「九進位」的九個符號,就像我們從沒發明「4」這個數字一樣。

而「T」代表要把給定的數字轉成這種「九進位」(少了「4」的 0 ~ 9 ),「F」則是代表把一個「九進位」數字轉成我們一般的十進位數字。




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

創作回應

更多創作