#45306: cpp 超級簡單解


1121232@stu.wghs.tp.edu.tw (Ian911436)

學校 : 臺北市私立薇閣高級中學
編號 : 258883
來源 : [60.248.154.139]
最後登入時間 :
2025-03-12 12:40:49
e995. string again!! -- it's david | From: [60.248.154.139] | 發表日期 : 2025-02-11 12:43

#include <iostream>

using namespace std;

// 計算從 1 到 x 的所有數字拼接後的總長度
long long f(long long x) {
    long long L = 0, B = 1, D = 1;
    while (B <= x) {
        long long U = min(x, B * 10 - 1);
        L += (U - B + 1) * D;
        B *= 10;
        D++;
    }
    return L;
}

// 找出第 n 個數位
int g(long long n) {
    // 1. **二分查找 `n` 落在哪個數字中**
    long long L = 1, R = 2000000000, X;
    while (L < R) {
        long long M = (L + R) / 2;
        if (f(M) < n)
            L = M + 1;
        else
            R = M;
    }
    X = L;  // 找到 `n` 所在的數字

    // 2. **找到 `n` 在該數字的第幾位**
    long long P = f(X - 1);
    
    // 確保不會存取非法索引
    if (n <= P) return -1;

    string S = to_string(X);
    
    return S[n - P - 1] - '0';  // 回傳對應的數位
}

int main() {
    long long n;
    while (cin >> n) {
        int res = g(n);
        if (res != -1)
            cout << res << endl;
    }
    return 0;
}

 
ZeroJudge Forum