ARC118-A Tax Included Price

問題へのリンク

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 1");
            //10
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 5");
            //171
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 1000000000");
            //100999999999
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static decimal mT;
    static decimal mN;

    static void Main()
    {
        List<string> InputList = GetInputList();
        decimal[] wkArr = InputList[0].Split(' ').Select(pX => decimal.Parse(pX)).ToArray();
        mT = wkArr[0];
        mN = wkArr[1];

        //DerivePriceHasTax(10);
        //DeriveLowerBound(10);
        //return;

        // 二分法で、税込価格までに未登場な数がN以上な、最小の税抜価格を求める
        decimal L = 0;
        decimal R = mN * 100;

        while (L + 1 < R) {
            decimal Mid = (L + R) / 2;
            Mid = Math.Truncate(Mid);

            decimal NonAppearCnt = DeriveNonAppearCnt(Mid);
            if (mN <= NonAppearCnt) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }

        decimal CurrPriceHasTax = DerivePriceHasTax(R);
        decimal Rest = (CurrPriceHasTax - R) - mN + 1; // 後ろから探す
        while (Rest > 0) {
            CurrPriceHasTax--;
            decimal LowerBound = DeriveLowerBound(CurrPriceHasTax);

            if (LowerBound != CurrPriceHasTax) {
                Rest--;
            }
        }
        Console.WriteLine(CurrPriceHasTax);
    }

    // 税抜価格を引数として、税込価格を求め、
    // 税込価格までに未登場な数が何通りあるかを返す
    static decimal DeriveNonAppearCnt(decimal pPriceNotHasTax)
    {
        decimal PriceHasTax = DerivePriceHasTax(pPriceNotHasTax);
        return PriceHasTax - pPriceNotHasTax;
    }

    // 引数の値以上で、最小の税込価格を返す
    static decimal DeriveLowerBound(decimal pVal)
    {
        decimal L = 0;
        decimal R = pVal * 100;

        while (L + 1 < R) {
            decimal Mid = (L + R) / 2;
            Mid = Math.Truncate(Mid);

            decimal PriceHasTax = DerivePriceHasTax(Mid);
            if (pVal <= PriceHasTax) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return DerivePriceHasTax(R);
    }

    // 税抜価格を引数として、税込価格を返す
    static decimal DerivePriceHasTax(decimal pVal)
    {
        decimal PriceHasTax = pVal + pVal * (mT / 100);
        PriceHasTax = Math.Truncate(PriceHasTax);
        return PriceHasTax;
    }
}

解説

税率50%だと
税抜500円は、税込525円になり、
これは、税込525円までに、未登場な税込価格が25通りあることを意味します。
(鳩の巣原理で、鳩が500羽で、鳩の巣が525個のため)

税抜価格が増えるほど、未登場な税込価格が増えるので
未登場な税込価格がN通り以上になる、最小の税抜価格を二分法で求めます。

その後は、指定の税抜価格が、登場するかの判定は二分法で行いつつ
N番目の未登場な税込価格を順に調べてます。

なお、異なる税抜き価格に課税し、同じ税込価格になることはないです。
例えば、税抜き価格100円と101円であれば、
税は、同じか後者のほうが多いという状態で、
100円+税
101円+税
という税込価格になるためです。