第13回PAST K 整数屋さん

問題へのリンク

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("3 4 50");
            //12
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("199 211 10000000000");
            //50251233
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        long A = wkArr[0];
        long B = wkArr[1];
        long X = wkArr[2];

        long RestMoney = X;
        long Omomi = 1000000000;

        // 1000000000を買える場合
        if (A * Omomi + B <= X) {
            Console.WriteLine(Omomi);
            return;
        }

        long Answer = 0;
        while (Omomi > 0) {
            for (long I = 9; 1 <= I; I--) {
                long Cost = A * I * Omomi + I * B;
                if (RestMoney >= Cost) {
                    Answer += I * Omomi;
                    RestMoney -= Cost;
                    break;
                }
            }
            Omomi /= 10;
        }
        Console.WriteLine(Answer);
    }
}

解説

1から1000000000の整数が売られていて、
なるべく大きな整数を購入したいのですから、

まずは、1000000000を購入できるか調べ、
購入できるならそれが解です。

購入できない場合は、
最上位桁から1の位までの順に、
9から1の順で。「買えるなら買う」を繰り返す貪欲法で解けます。