Pythonで飲めるウォーターボトルの最大本数を求めるプログラム

問題概要

満杯の水ボトルが n 本あるとします。ここで、空きボトル m 個 を交換すると満杯のボトル 1 本と引き換えられるというルールがあります。満杯のボトルを飲むと、そのボトルは空きボトルになります。このとき、合計で最大何本の水ボトルを飲めるかを求めるのがこの問題です。

具体例

たとえば、入力が n = 9、m = 3 の場合、出力は 13 になります。その理由は以下の通りです。

• 最初に 9 本の満杯ボトルがあり、すべて飲むと 9 本の空きボトルになります。
• 9 ÷ 3 = 3 なので、空きボトル 9 個から満杯ボトル 3 本と交換できます。
• その 3 本をすべて飲むと、再び空きボトルが 3 個手に入ります。
• さらに 3 個の空きボトルで満杯ボトル 1 本と交換し、それを飲みます。
• 合計は 9 + 3 + 1 = 13 本 となります。

解法のアプローチ

この問題は、次の手順で解くことができます。

• x := n（現在のボトル数）、s := 0（交換で得たボトル数の累計）、k := 0（余り）として初期化します。
• x >= m の間、以下を繰り返します。
  • k := x mod m：交換に使えない余りの空きボトル数を求めます。
  • x := x / m の商：交換して得られる新しい満杯ボトル数を計算します。
  • s := s + x：新たに得られたボトル数を累計に加算します。
  • x := x + k：飲んだ分の空きボトルと余りを合算します。
• 最後に n + s を返します。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

def solve(n, m):
    x = n
    s = 0
    k = 0
    while x >= m:
        k = x % m
        x = x // m
        s = s + x
        x = x + k
    return n + s

n = 9
m = 3
print(solve(n, m))

入力

9, 3

出力

13

まとめ

このアルゴリズムは、ボトルの交換プロセスを単純なループでシミュレートするものです。各ループで現在の空きボトルを可能な限り交換し、余りを保持しながら処理を繰り返すことで、飲めるボトルの総本数を効率的に求められます。ループごとにボトル数が m 分の 1 になっていくため、計算量は O(log n) 程度と非常に効率的です。