b897: 10219 - Find the ways !

內容

一個美國人、一個法國人、和一個英國人來到了孟加拉的首都達卡。他們搭計乘車去觀光。三個觀光客聊起了城市的景觀。那個美國人為紐約的高聳建築感到騎傲。他對朋友們吹噓：「你知道帝國大廈只花了三個月就蓋好了嗎？」

「真的？」法國人說：「巴黎的艾菲爾鐵塔一個月就蓋好了呢！」(然而事實上，鐵塔於 1887 年一月動工。40 個工程師和設計師在艾菲爾的指導下工作了兩年。鐵塔於 1989 年三月完成。)

「真有趣！」英國人說：「倫敦的白金漢宮兩個星期就蓋好了！」

這時計程車經過了一個大型貧民窟 (然而，在孟加拉我們稱之為 Bostii)。「那是什麼？什麼時候蓋的？」英國人問那孟加拉司機。

「我不知道！」司機回答說：「昨天還沒看到呀！」。

在孟加拉，非法貧民窟的存在一直是個大問題。政府一直試著拆除這些貧民窟並將其中居民正式安置於市郊的重劃區。但是他們找不到任何的方法來拆除這些貧民窟！

現在，你能想像你是貧民窟的拆除者嗎？要將 k 個貧民窟中的 n 個貧民窟拆除有幾種方法？假設有 10 個貧民窟，你獲准拆除其中的 5 個，你有 252 個方式，這只是個 3 位數字。你的工作就是找出拆除貧民窟的方法數是幾位數字。

輸入

輸入檔含有一筆或多筆測資。

每筆測資一行，含有兩個整數 n (n ≥ 1) 及 k (1 ≤ k ≤ n)。

20 5
100 10
200 15

輸出

針對每筆測資，輸出一個所要求的數字於一行。這個數字可存於一個整數，也就是它小於 2³¹ − 1。

5
14
23

解題思路

數學題，有 3 個重點公式

1. Log(a * b) = Log(a) + Log(b)
2. Log(a / b) = Log(a) - Log(b)
3. n 的位數 = Floor(Log₁₀n) + 1

然後如以下範例展開

以 10! / 4! 為例，將階層展開

(10 * 9 * 8 * 7) / (6 * 5 * 4 * 3)

取 Log

Log₁₀(10 * 9 * 8 * 7 / 4 * 3 * 2 * 1)

因為公式 1 和 2 所以可以再將它展開成

(Log₁₀10 + Log₁₀9 + Log₁₀8 + Log₁₀7) - (Log₁₀4 + Log₁₀3 + Log₁₀2 + Log₁₀1)

又因為公式 3 所以位數就是

Floor(Log₁₀10 + Log₁₀9 + Log₁₀8 + Log₁₀7 - Log₁₀4 - Log₁₀3 - Log₁₀2 - Log₁₀1) + 1

計算結果

Floor(1 + 0.954 + 0.903 + 0.845 - 0.602 - 0.477 - 0.301 - 0) + 1
= Floor(2.322) + 1 = 2 + 1 = 3
就能得到它的位數了。

接下來就是簡單的把公式轉換成程式碼，取階層時記得取小的那區即可。

完整程式碼

AC (66ms, 176KB)

#include <stdio.h>
#include <math.h>

int main()
{
    register double log;
    int n, k, max;
    while (scanf(" %d %d", &k, &n) == 2)
    {
        log = 0, max = n < k - n ? n : k - n;
        for (int i = 0; i < max; i++)
            log += log10(k - i) - log10(i + 1);
        printf("%d\n", (int)log + 1);
    }
    return 0;
}