ABC085-C Otoshidama

■■■問題■■■

日本でよく使われる紙幣は、10000円札、5000円札、1000円札です。
以下、「お札」とはこれらのみを指します。

青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札がN枚入っていて、
合計でY円だったそうですが、嘘かもしれません。

このような状況がありうるか判定し、
ありうる場合はお年玉袋の中身の候補を一つ見つけてください。
なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

■■■入力■■■

N Y

●1 <= N <= 2000
●1000 <= Y <= 2000万
●Nは整数である
●Yは1000の倍数である

■■■出力■■■

N枚のお札の合計金額がY円となることがありえない場合は、-1 -1 -1 と出力せよ。

N枚のお札の合計金額がY円となることがありうる場合は、
そのようなN枚のお札の組み合わせの一例を「10000円札x枚、5000円札y枚、1000円札z枚」として、
x、y、z を空白で区切って出力せよ。
複数の可能性が考えられるときは、そのうちどれを出力してもよい。

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("9 45000");
            //4 0 5
            //お年玉袋に10000円札4枚と1000円札5枚が入っていれば、
            //合計枚数が9枚、合計金額が45000円になります。
            //5000円札9枚という可能性も考えられるため、0 9 0 も正しい出力です。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("20 196000");
            //-1 -1 -1
            //合計枚数が20枚の場合、
            //すべてが10000円札であれば合計金額は200000円になり、
            //そうでなければ195000円以下になるため、196000円という合計金額はありえません。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1000 1234000");
            //14 27 959
            //この他にも多くの候補があります。
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("2000 20000000");
            //2000 0 0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        for (long I = 0; I <= N; I++) {
            long SumVal = 10000 * I;
            if (SumVal > Y) break;
            for (long J = 0; I + J <= N; J++) {
                SumVal = 10000 * I + 5000 * J;
                long Rest = Y - SumVal;

                if (Rest < 0) break;
                if (Rest % 1000 > 0) continue;
                long K = Rest / 1000;

                if (I + J + K == N) {
                    Console.WriteLine("{0} {1} {2}", I, J, K);
                    return;
                }
            }
        }
        Console.WriteLine("-1 -1 -1");
    }
}

解説

計算量削減のため、2重ループで解いてます。