HDU 1330 Deck：找規律遞推求紙牌最大懸空距離

HDU 1330 Deck：找規律遞推求紙牌最大懸空距離

問題描述

桌面疊紙牌，每張長 1。第 1 張最多懸空 1/2。第 2 張在第一張上再懸空 1/4，總懸空 3/4。第 3 張總懸空 11/12。求 n 張紙牌最大懸空距離（以紙牌長度為單位），保留 3 位小數。n ≤ 99999。

規律推導

第 n 張新增懸空 = 1/(2n)。
總懸空 a[n] = a[n-1] + 1/(2n)，a[1] = 0.5。
即 a[n] = 1/2 * (1 + 1/2 + 1/3 + ... + 1/n) = 調和級數 / 2。

預計算 + 格式化輸出

#include <stdio.h>
double a[100000];

int main() {
    a[1] = 0.5;
    for (int i = 2; i < 100000; i++)
        a[i] = a[i-1] + 1.0 / (2*i);
    printf("# Cards Overhang\n");
    int n;
    while (~scanf("%d", &n))
        printf("%5d%10.3lf\n", n, a[n]);
    return 0;
}

輸出格式細節

• 標題行：`# Cards Overhang`（兩空格）
• 數據行：編號右對齊寬度 5，小數點列 12，保留 3 位小數
• `%5d%10.3lf` 完美匹配

Sample I/O

Input: 1 2 3 4 30
Output:
# Cards Overhang
    1     0.500
    2     0.750
    3     0.917
    4     1.042
   30     1.997

複雜度

預計算 O(N)，查詢 O(1)，N=10⁵ 極快。