【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e294
【解題想法】
- 要找出最靠近 N 的完全奇數 K，
- 因為要「最靠近 N」：從高位數開始檢查，遇到偶數再處理。
- K 比 N 大：把第一個遇到的偶數加 1，後續位數全部換成 1 (最小的奇數)。
- K 比 N 小：把第一個遇到的偶數減 1，後續位數全部換成 9 (最大的奇數)。如果第一個遇到的偶數是 0，需要一路借位，從更高的位數減 2 (保持其奇數狀態)。
#include <iostream>
#include <cstring>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
int a[20] = {};
long long N, N1, N2;
while (cin >> s){
int len = s.size();
N = 0;
for (int i=0; i<len; i++){
N *= 10;
N += s[i] - '0';
}
// N1: 比 N 大的完全奇數
memset(a, 0, sizeof(a));
for (int i=0; i<len; i++){
int x = (s[i] - '0');
if (x % 2 == 0){
a[i] = x + 1;
for (int j=i+1; j<len; j++) a[j]=1;
break;
} else {
a[i] = x;
}
}
N1 = 0;
for (int i=0; i<len; i++){
N1 *= 10;
N1 += a[i];
}
// N2: 比 N 小的完全奇數
memset(a, 0, sizeof(a));
for (int i=0; i<len; i++){
int x = (s[i] - '0');
if (x % 2 == 0){
if (x == 0) {
a[i] = 9;
int idx = i - 1;
while (idx > 0 && a[idx] == 1){
a[idx] = 9;
idx--;
}
a[idx] -= 2;
if (a[idx] < 0) a[idx] = 0;
} else {
a[i] = x - 1;
}
for (int j=i+1; j<len; j++) a[j]=9;
break;
} else {
a[i] = x;
}
}
N2 = 0;
for (int i=0; i<len; i++){
N2 *= 10;
N2 += a[i];
}
cout << min(N1 - N, N - N2) << '\n';
}
return 0;
}
Python code (credit: Amy Chou)
while True:
try:
s = input()
a = [int(c) for c in s]
N = int(s)
# N1: 比 N 大的完全奇數
b = [0 for _ in range(len(s))]
for i in range(len(a)):
if a[i] % 2 == 0:
b[i] = a[i] + 1
for j in range(i+1, len(a)):
b[j] = 1
break
else:
b[i] = a[i]
N1 = int(''.join([str(i) for i in b]))
# N2: 比 N 小的完全奇數
b = [0 for _ in range(len(s))]
for i in range(len(a)):
if a[i] % 2 == 0:
if (a[i] == 0):
b[i] = 9
idx = i - 1
while idx > 0 and a[idx] == 1:
b[idx] = 9
idx -= 1
b[idx] -= 2
if b[idx] < 0:
b[idx] = 0
else:
b[i] = a[i] - 1
for j in range(i+1, len(a)):
b[j] = 9
break
else:
b[i] = a[i]
N2 = int(''.join([str(i) for i in b]))
print(min(N1 - N, N - N2))
except:
break