AGC-014-A Cookie Exchanges

■■■問題■■■

高橋君と青木君とすぬけ君はそれぞれクッキーを A,B,C 個持っています。
この3人はお互いにクッキーを交換することにしました。具体的には、以下の操作を繰り返します。

●3人は同時に、各々が持っているクッキーを半分ずつに分けて、残りの2人にそれぞれ一方を渡す。

ただし、誰かの持っているクッキーの個数が奇数個になったら、そこで操作を繰り返すのをやめます。

さて、クッキーの交換は何回行うことができるでしょうか。
ただし、無限に続けられる場合もあることに注意してください。

■■■入力■■■

A B C

●1 <= A,B,C <= 10億

■■■出力■■■

3人がクッキーの交換を行うことができる回数を出力せよ。
ただし、無限に続けられる場合は-1を出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4 12 20");
            //3
            //はじめ、高橋君と青木君とすぬけ君はそれぞれクッキーを 4,12,20 個持っており、
            //1回目の操作後は、高橋君と青木君とすぬけ君はそれぞれクッキーを16,12, 8個持っている。
            //2回目の操作後は、高橋君と青木君とすぬけ君はそれぞれクッキーを10,12,14個持っている。
            //3回目の操作後は、高橋君と青木君とすぬけ君はそれぞれクッキーを13,12,11個持っている。
            //3回目の操作後に高橋君とすぬけ君の持っているクッキーの個数が奇数個になるので、
            //求める回数は3回となります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("14 14 14");
            //-1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("454 414 444");
            //1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();

        long A = wkArr[0];
        long B = wkArr[1];
        long C = wkArr[2];

        int Answer = 0;
        var VisitedSet = new HashSet<string>();
        VisitedSet.Add(GetHash(A, B, C));

        while (true) {
            if (A % 2 == 1 || B % 2 == 1 || C % 2 == 1) {
                break;
            }

            ExecExchange(ref A, ref B, ref C);
            if (VisitedSet.Add(GetHash(A, B, C)) == false) {
                Answer = -1;
                break;
            }
            Answer++;
        }
        Console.WriteLine(Answer);
    }

    static void ExecExchange(ref long pA, ref long pB, ref long pC)
    {
        long NewA = (pB + pC) / 2;
        long NewB = (pA + pC) / 2;
        long NewC = (pA + pB) / 2;

        pA = NewA;
        pB = NewB;
        pC = NewC;
    }

    static string GetHash(long pA, long pB, long pC)
    {
        return string.Format("{0},{1},{2}", pA, pB, pC);
    }
}

解説

ナイーブにシュミレーションしてます。