2つのバケツ

説明

大きさの異なる2つのバケットと、どちらを先に満たすかが与えられたとき、バケット間で戦略的に液体を移し替えて、正確なリットル数を量るには何回の操作が必要かを求めます。

解答が従わなければならないルールがいくつかあります。

• 一度にできる操作は1つだけです。
• 可能な操作は次の3つだけです。
  1. 一方のバケットをもう一方のバケットに、次のいずれかの状態になるまで注ぐ。 a) 最初のバケットが空になる b) 2つ目のバケットがいっぱいになる
  2. 一方のバケットを空にし、もう一方には何もしない。
  3. 一方のバケットを満たし、もう一方には何もしない。
• 操作の後、最初の開始バケットが空で、もう一方のバケットがいっぱいである状態になってはいけません。

プログラムは次のものを入力として受け取ります。

• バケット1の大きさ
• バケット2の大きさ
• 目的のリットル数
• どちらのバケットを先に満たすか（バケット1かバケット2のいずれか）

プログラムは次のことを求める必要があります。

• 目的のリットル数に達するまでにかかる操作の総数（開始バケットを最初に満たす操作を含む）
• 最終的に目的のリットル数が入っているバケット（バケット1かバケット2のいずれか）
• もう一方のバケットに何リットル残っているか

注意: どちらか一方、または両方のバケットに変化が生じるたびに、1回の操作として数えます。

例: バケット1には最大7リットル、バケット2には最大11リットル入ります。 ある時点で、バケット1に7リットル、バケット2に8リットル入っているとします（7,8）。 バケット1を空にし、バケット2には何もせず、それぞれ0リットルと8リットル（0,8）になったとすると、これは1回の操作として数えます。 逆に、バケット2がいっぱいになるまでバケット1からバケット2へ注ぎ、その結果バケット1に4リットル、バケット2に11リットル（4,11）になったとしても、これも1回の操作としてしか数えません。

もう1つの例: バケット1には3リットル、バケット2には最大5リットル入ります。 ここでは、バケット1から始めなければならないとします。 すると、最初の操作はバケット1を満たすことになります。 2回目の操作として、バケット1を空にすることにします。 3回目の操作でバケット2を満たすことはできません。これは3つ目のルールに反するからです。どのような操作の後でも、開始バケットが空でもう一方のバケットがいっぱいである状態になってはいけません。

Fullstack AcademyのLindsay Levineが<3を込めて書きました。

---

出典

水差し問題