主題

ZeroJudge - c079: 10346 - Peter's Smokes 解題心得

Not In My Back Yard | 2021-04-11 02:00:01 | 巴幣 0 | 人氣 57

題目連結:


題目大意:
輸入有多列,每列給定兩正整數 n 、 k。代表著 Peter 原先有 n 支菸,每支菸抽完後會有一份菸屁股,每 k 份菸屁股可以捲成一支新的菸。

試問 Peter 最多可以抽多少支菸?



範例輸入:
4 3
10 3
100 5


範例輸出:
5
14
124


解題思維:
本題模擬即可—— n 支菸抽完後變成 n 份菸屁股,每 k 份換一支新的菸然後抽掉變成菸屁股,重複此步驟直到手頭有的菸屁股數量 < k。途中抽的菸數即是所求。



不過,本題有著一個神祕的公式解,即所求 =
n + floor((n - 1) ÷ (k - 1))
其中 floor() 代表下高斯,即向下取整(對於正的數字來說即無條件捨去)。

原本模擬的過程,其等價於求下式
n + floor(n ÷ k) + floor(n ÷ (k ^ 2)) + ……
但是難以(至少需要寫不少步驟)證明其等價於公式。



不過,實際上有一個相當精巧的文字敘述之證明,其內容如下:
我們將原先的 n 支菸抽掉得到 n 份菸屁股。

此時,我們先拿走一個菸屁股,因此剩下 n - 1 份菸屁股。

因為每 k 份菸屁股可以組成一支菸,因此我們接著從 n - 1 份菸屁股裡拿走 k - 1 份菸屁股與剛剛預先拿走的那一份菸屁股組合成一支菸然後抽掉。抽掉之後,會留下一份菸屁股。

而留下的菸屁股就仿照上述的做法,從剩下的菸屁股堆拿 k - 1 份與該份組合並抽掉。抽掉之後又會剩下一份菸屁股。因此,我們就重複此步驟直到菸屁股堆的數量不足 k - 1 為止。

因此,過程中抽的菸數恰好為
n + floor((n - 1) ÷ (k - 1))
得證。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作