[UVA] 10346 Peter Smokes

題目大義如下：

    Peter愛抽煙，他發現每抽K根煙，抽剩的K個煙屁股可以再捲成一根煙。今天有N根 煙，請問Peter總共可以抽幾次？

    這一題用simulation解非常簡單，原則上就是:
ANS = N + floor(N / K) + floor( N / K^2) + floor( N / K^3) + ....

   的數列和，而floor()是取round down的整數部份。O(logN)的效率還是不錯，不過經CL提點這題有O(1)解法，花了幾個小時狂試，發現居然真的有formula解:

ANS = N + floor( (N - 1) / (K - 1))

   我是作弊先把函數圖畫出來，再歸納出公式，所以並不是正統的邏輯推導得出的答案。我自己對這個公式的解釋是:

    N的部份就是原祖煙。而多出來的部份可以這樣想：抽完的N個煙屁股中，每K個煙屁股可以集中產生一支煙，然後丟棄K-1個煙屁股。這個集中 -- 回收 -- 丟棄的process可以移除 K - 1個煙屁股。這樣可以解釋分母 K - 1的由來，不過N - 1的部份我無法說明。後來經CL解答，才知道可以想成：把第一個煙屁股當做煙 斗，然後每 K - 1 根煙屁股可以跟煙斗合體再抽一次，抽完後剩下煙斗自己 ( K = >  1 )，所以總共有 1個煙斗，N - 1個煙屁股，每 K - 1個煙屁股可以再抽一次，而多抽的次數就是 (N - 1) / (K -1)。非常優雅的證明，也讓我見視到人跟神的差距。