主題

ZeroJudge - d189: 11150 - Cola 解題心得

Not In My Back Yard | 2021-04-12 00:00:09 | 巴幣 0 | 人氣 47

題目連結:


題目大意:
輸入有多列,每列給定一正整數 N (1 ≦ N ≦ 200),代表原先有 N 瓶可樂。每瓶可樂喝完後會剩一個空瓶,每 3 瓶可以換一瓶新的可樂。

而你可以預先借來一些空瓶,使得自己可以換得更多的可樂來喝(如下圖)。不過最後需要還相應數量的空瓶。

試問最多可以喝多少瓶可樂?



範例輸入:
8
9


範例輸出:
12
13


解題思維:
很像昨天的題目,但是這次我們可以借一些空瓶。

不過仔細觀察後,我們可以發現借 2 瓶(含)以上的空瓶不會比完全不借來得好(也就是不借反而比較直接),而借 1 瓶不會比不借來得差。而這可以藉由昨天的論述來看出:
因為每 3 瓶空瓶換 1 瓶可樂,所以我們將原本的 N 瓶可樂變為 3N 瓶空瓶。

接著我們預先拿走 1 瓶空瓶,接著從剩下的空瓶裡每次拿 2 瓶空瓶與剛剛預先拿走的空瓶換成 1 瓶可樂,因此喝完後又得到 1 瓶空瓶。重複直到空瓶總數 < 3 瓶為止。

已知 3N - 1 除以 2 的餘數只會是 0 或是 1。

先看為何借 2 瓶空瓶不會比較好:
當餘數 = 0 時,因為要還相應數量的空瓶,所以基本上借了就得馬上還(因為拿去換去換的話就沒空瓶可以還了)。

當餘數 = 1 時,此時借來的其中 1 瓶 + 手上預先拿著的空瓶 + 餘數的那瓶可以湊成 1 瓶可樂,因此又回來 1 瓶空瓶。但是借的另 1 瓶形同無用,最後還是會被還回去。

而借 > 2 瓶也是同理。而且從上我們可以看到如果只借 1 瓶最後一定有辦法還,因為你手上必定隨時拿著 1 個空瓶(根據昨天的論述)。

因此借 1 瓶只會更好,因此本題的公式解為
floor(3N ÷ 2)
其中 floor() 代表下高斯,即向下取整(對於正的數字來說即無條件捨去)。




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

創作回應

相關創作

更多創作