using System;

using System.Collections.Generic;

using System.Linq;

​

namespace MoneyPermutation

{

    public class Program

    {

        private static IList<int> s_availableAmounts = new int[] {

            500, 1000, 2000, 5000, 10000, 20000, 50000

        };

​

        static long NumberOfWaysToPay(long bill)

        {

            // Simplify input

            var gcd = s_availableAmounts.First();

            var bank = s_availableAmounts.Select(amount => amount / gcd).ToArray();

            bill = bill / gcd;

​

            // Prepare array for dynamic programming solution.

            var dp = new long[bank.Length, bill+1];

​

            // Fill table from top left to bottom right.

            for (var i = 0; i < bank.Length; ++i)

            {

                var v = bank[i];

                for (long j = 0; j <= bill; ++j)

                {

                    var prev_j = j - v;

                    if (prev_j > 0)

                    {

                        for (var k = 0; k <= i; ++k)

                        {

                            dp[i, j] += dp[k, prev_j];

                        }

                    }

                    else if (prev_j == 0)

                    {

                        dp[i, j] = 1;

                    }

                }

            }

​

            // Assemble result by summing last column.

            long result = 0;

            for (var i = 0; i < bank.Length-1; ++i) result += dp[i, bill];

            return result;

        }

​

​

        public static int Main(string[] args)

        {

            args = new String[] {"2000"}; // for .NET Fiddle only

            var billArgument = args.FirstOrDefault();

            if (billArgument == null)

            {

                Console.WriteLine("No argument provided.");

                return 1;

            }

​

            long bill;

            if (!long.TryParse(billArgument, out bill) || bill % s_availableAmounts.First() != 0)

            {

                Console.WriteLine(string.Format(

                    "Argument is not a valid integer that is divisible by {0}.",

                    s_availableAmounts.First()));

                return 1;

            }

​

            // Actual calculation.

            var result = NumberOfWaysToPay(bill);

​

            Console.WriteLine(

                "Number of ways to pay bill of {0} VND using one of ({1}) VND banknotes:\n{2}",

                bill,

                string.Join(", ", s_availableAmounts),

                result);

​

            return 0;

        }

    }

}

​