#18359: APCS 類似題 - 小崴的新發現


yotrew (熾翼)

School : No School
ID : 5520
IP address : [111.242.152.199]
Last Login :
2022-06-27 15:39:57
e294. APCS 類似題 - 小崴的新發現 -- 小崴系列APCS | From: [1.172.79.162] | Post Date : 2019-07-06 19:58

 解法,將輸入數字(N)拆解成一個一個數字

此解法應該是O(2*M),M為N的長度,此題最大值為10^18,因此O(36)就可以解決了

本題為求最接近此數的完全奇數
因此有2種情況,一個比此數大,一個比此數小,就把這兩個數求出來,再比較它們距離N的距離何者最小,
這2數的求法:
1. 大數:就從左自右掃,掃到某位數為偶數,把此位數加1(因為最小偶數為8,加1變9,所以沒進位問題),此位數之後的數都為1,則此數比N大的最小值
ex. 134567  =>   13(4+1)111
ex. 13256 -> 13(2+1)11 -> 13311
2. 小數:就從左自右掃,掃到某位數為偶數,把此位數減1(因為最小偶數為0,扣1之後要向前一位借位,此位數假設為最後一位,且前面所有數都為1,就要借到最前位,所以是O(18+18)),
此位數之後都為9,則此數比N小的最因值
ex. 111111102 -> 1111111(0-1)9 ->向前借 999999(9)9
ex. 35001 -> 3[5-2](0-1)99 ->3[3](9)99 
ex. 13256 -> 13(2-1)99 -> 13199

 
#24681: Re:APCS 類似題 - 小崴的新發現


joanyang2011 (安)

School : No School
ID : 141867
IP address : [163.19.254.179]
Last Login :
2022-04-23 14:49:33
e294. APCS 類似題 - 小崴的新發現 -- 小崴系列APCS | From: [163.19.254.182] | Post Date : 2021-03-14 13:04

 解法,將輸入數字(N)拆解成一個一個數字

此解法應該是O(2*M),M為N的長度,此題最大值為10^18,因此O(36)就可以解決了

本題為求最接近此數的完全奇數
因此有2種情況,一個比此數大,一個比此數小,就把這兩個數求出來,再比較它們距離N的距離何者最小,
這2數的求法:
1. 大數:就從左自右掃,掃到某位數為偶數,把此位數加1(因為最小偶數為8,加1變9,所以沒進位問題),此位數之後的數都為1,則此數比N大的最小值
ex. 134567  =>   13(4+1)111
ex. 13256 -> 13(2+1)11 -> 13311
2. 小數:就從左自右掃,掃到某位數為偶數,把此位數減1(因為最小偶數為0,扣1之後要向前一位借位,此位數假設為最後一位,且前面所有數都為1,就要借到最前位,所以是O(18+18)),
此位數之後都為9,則此數比N小的最因值
ex. 111111102 -> 1111111(0-1)9 ->向前借 999999(9)9
ex. 35001 -> 3[5-2](0-1)99 ->3[3](9)99 
ex. 13256 -> 13(2-1)99 -> 13199

dj04ai6,

vu;4x96e83j84

 

194w.7a87

 
ZeroJudge Forum