【題解】ZeroJudge e294: APCS 類似題 – 小崴的新發現

【題目敘述】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
分享本文 Share with friends