Q44 グラスの水を半分に

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int AnswerCnt = 0;
        for (int A = 10; A <= 100; A += 2) {
            for (int B = 1; B < A; B++) {
                for (int C = 1; C < B; C++) {
                    if (B + C != A) continue;
                    if (DeriveGCD(B, C) != 1) continue;

                    if (IsAnswer(A, B, C)) AnswerCnt++;
                }
            }
        }
        Console.WriteLine(AnswerCnt);
    }

    //ユークリッドの互除法で2数の最大公約数を求める
    static long DeriveGCD(int pVal1, int pVal2)
    {
        int WarareruKazu = Math.Max(pVal1, pVal2);
        int WaruKazu = Math.Min(pVal1, pVal2);

        while (true) {
            int Amari = WarareruKazu % WaruKazu;
            if (Amari == 0) return WaruKazu;
            WarareruKazu = WaruKazu;
            WaruKazu = Amari;
        }
    }

    struct JyoutaiDef
    {
        internal int CurrA;
        internal int CurrB;
        internal int CurrC;
        internal List<string> Log;
    }

    //Aを半分にできるかを判定
    static bool IsAnswer(int pLimitA, int pLimitB, int pLimitC)
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrA = pLimitA;
        WillPush.CurrB = WillPush.CurrC = 0;
        WillPush.Log = new List<string>();

        string wkStr1 = ABCToStr(WillPush.CurrA, WillPush.CurrB, WillPush.CurrC);
        WillPush.Log.Add(wkStr1);
        stk.Push(WillPush);

        var VisitedSet = new HashSet<string>() { wkStr1 };
        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //クリア判定
            if (Popped.CurrA * 2 == pLimitA) {
                //Console.WriteLine("Aを半分にする手順");
                //Popped.Log.ForEach(X => Console.WriteLine(X));
                return true;
            }

            Action CopyAct = () =>
            {
                WillPush.CurrA = Popped.CurrA;
                WillPush.CurrB = Popped.CurrB;
                WillPush.CurrC = Popped.CurrC;
            };

            Action PushSyori = () =>
            {
                string wkStr2 = ABCToStr(WillPush.CurrA, WillPush.CurrB, WillPush.CurrC);
                if (VisitedSet.Add(wkStr2) == false) return;

                WillPush.Log = new List<string>(Popped.Log);
                WillPush.Log.Add(wkStr2);
                stk.Push(WillPush);
            };

            CopyAct();
            if (MoveWater(ref WillPush.CurrA, ref WillPush.CurrB, pLimitB)) {
                PushSyori();
            }
            CopyAct();
            if (MoveWater(ref WillPush.CurrA, ref WillPush.CurrC, pLimitC)) {
                PushSyori();
            }
            CopyAct();
            if (MoveWater(ref WillPush.CurrB, ref WillPush.CurrA, pLimitA)) {
                PushSyori();
            }
            CopyAct();
            if (MoveWater(ref WillPush.CurrB, ref WillPush.CurrC, pLimitC)) {
                PushSyori();
            }
            CopyAct();
            if (MoveWater(ref WillPush.CurrC, ref WillPush.CurrA, pLimitA)) {
                PushSyori();
            }
            CopyAct();
            if (MoveWater(ref WillPush.CurrC, ref WillPush.CurrB, pLimitB)) {
                PushSyori();
            }
        }
        return false;
    }

    //A,B,CをString型で表現
    static string ABCToStr(int pA, int pB, int pC)
    {
        return string.Format("{0},{1},{2}", pA, pB, pC);
    }

    //FromからToに水を移す
    static bool MoveWater(ref int pFrom, ref int pTo, int pToLimit)
    {
        int MoveWater = Math.Min(pFrom, pToLimit - pTo);
        if (MoveWater == 0) return false;

        pFrom -= MoveWater;
        pTo += MoveWater;
        return true;
    }
}

実行結果

514

解説

A,B,Cの組み合わせごとに、深さ優先探索してます。