ABC146-C Buy an Integer

問題へのリンク

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("10 7 100");
            //9
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 1 100000000000");
            //1000000000
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1000000000 1000000000 100");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("1234 56789 314159265");
            //254309
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mA;
    static long mB;
    static long mX;

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

        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mA = wkArr[0];
        mB = wkArr[1];
        mX = wkArr[2];

        // 二分法で解く
        long L = 0;
        long R = 1000000000;

        if (DerivePrice(R) <= mX) {
            Console.WriteLine(R);
            return;
        }

        while (L + 1 < R) {
            long Mid = (L + R) / 2;

            long Price = DerivePrice(Mid);

            if (Price <= mX) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        Console.WriteLine(L);
    }

    // 整数Nの価格を返す
    static long DerivePrice(long pN)
    {
        return mA * pN + mB * DeriveKetaSuu(pN);
    }

    // 整数Nの桁数を返す
    static long DeriveKetaSuu(long pTarget)
    {
        if (pTarget == 0) return 0;
        if (pTarget <= 9) return 1;
        if (pTarget <= 99) return 2;
        if (pTarget <= 999) return 3;
        if (pTarget <= 9999) return 4;
        if (pTarget <= 99999) return 5;
        if (pTarget <= 999999) return 6;
        if (pTarget <= 9999999) return 7;
        if (pTarget <= 99999999) return 8;
        if (pTarget <= 999999999) return 9;
        return 10;
    }
}

解説

整数の価格は、整数の値に対し、広義単調増加なので
二分法を使ってます。