ABC180-D Takahashi Unevolved

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("4 20 2 10");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 1000000000000000000 10 1000000000");
            //1000000007
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        decimal[] wkArr = InputList[0].Split(' ').Select(pX => decimal.Parse(pX)).ToArray();
        decimal X = wkArr[0];
        decimal Y = wkArr[1];
        decimal A = wkArr[2];
        decimal B = wkArr[3];

        // A倍する回数を全探索
        decimal Answer = decimal.MinValue;
        decimal ProdX = X;
        for (decimal I = 0; I < int.MaxValue; I++) {
            if (I > 0) {
                ProdX *= A;
            }
            if (ProdX >= Y) break;

            decimal Rest = Y - 1 - ProdX;
            decimal ModVal = Rest % B;
            decimal DivVal = (Rest - ModVal) / B;

            Answer = Math.Max(Answer, I + DivVal);
        }
        Console.WriteLine(Answer);
    }
}

解説

例えば、
足し算を2回
掛け算を3回
するのであれば、
先に掛け算を3回してから、足し算を2回するのが最適なので、

掛け算の回数を全探索してます。