読者です 読者をやめる 読者になる 読者になる

C Sharpens you up

http://qiita.com/yuba に移しつつあります

コーディング課題・5ℓと3ℓのバケツで4ℓの水を用意する問題

CodeIQの問題・パズルを考えよう!(by CodeIQ×はてな

5リットルのバケツ(A)と3リットルのバケツ(B)だけ使って4リットルの水を測れと言われたら

  1. Aを満タンにする
  2. Aから注げるだけBに注いで、終わったらBの水は捨てる(Aに2リットルたまった)
  3. AからBに2リットルの水を移す
  4. Aを満タンにする
  5. AからBに注げるだけ注ぐと、Aに残るのは4リットル

これで最短手筋でしょうかね!?

はい、これを解くプログラムを書いてください。
問題は

バケツ容量はx, y(整数)
目標量はz(整数)

で与えられます。

許される操作は

  • どちらかを満タンにする
  • どちらかを空にする
  • 一方から他方へ注げるだけ注ぐ

のどれかです。

問題に対する結果として、

  • 手筋があるなら、操作を順序通りに返してください(操作を表現する形式はお任せします)。ただし最短のものです。
  • 手筋がないなら、空の結果を返してください。

例題の(5,3,4)に対しては

A.full
A.pour(B)
B.empty
A.pour(B)
A.full
A.pour(B)

という形の結果を出すということです。

応用問題

「なんのひねりもない*1幅優先探索じゃないの」と思った方、あなたは上位5%に入るエンジニアです。
そんなあなたに応用問題。

SQL SELECT文一本で解いてください。x,y,zにあたる数字は埋め込んでしまってかまいません。

*1:ひねっていないわけではなくて意地悪要素もあるんですがね。経路としてノード列でなくエッジ列を答えさせているところとか、解なし判定が必要なところとか。