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


yotrew (熾翼)

學校 : 不指定學校
編號 : 5520
來源 : [163.32.95.190]
最後登入時間 ：
2023-11-17 09:50:32
e294. APCS 類似題 - 小崴的新發現 -- 小崴系列APCS | From: [1.172.79.162] | 發表日期 : 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 (TLY)

學校 : 不指定學校
編號 : 141867
來源 : [59.120.188.205]
最後登入時間 ：
2024-10-23 14:40:02
e294. APCS 類似題 - 小崴的新發現 -- 小崴系列APCS | From: [163.19.254.182] | 發表日期 : 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

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


jason0713 ((ง⁼ω⁼)งꉂ(ˊᗜˋ*))

學校 : 不指定學校
編號 : 184210
來源 : [61.230.51.149]
最後登入時間 ：
2024-11-07 23:31:41
e294. APCS 類似題 - 小崴的新發現 -- 小崴系列APCS | From: [61.230.40.64] | 發表日期 : 2023-09-06 19:11

 解法，將輸入數字(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

好像變了......

 
ZeroJudge Forum