using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        double targetWeight = 23.7;

        Array.ForEach(Coin.Coins, x => Console.Write((x.Value + "yen").PadLeft(6)));
        Console.WriteLine(" : Total Amount");
        Console.WriteLine(new string('-', 52));

        var combinations = CoinCombination.GetGramMatched(targetWeight);
        int count = 0;
        foreach (var c in combinations)
        {
            foreach (var coin in Coin.Coins)
                Console.Write(c.GetCount(coin).ToString().PadLeft(6));
            Console.WriteLine(" : " + c.Value.ToString().PadLeft(12));
            count++;
        }
        Console.WriteLine(new string('-', 52));

        Console.WriteLine("Target Weight(Gram): " + targetWeight);
        Console.WriteLine("Number of Combinations: " + count);
        Console.ReadLine();
    }
}

public struct Coin
{
    public int Value { get; private set; }
    public double Gram { get; set; }

    // Gramの有効数字（小数点以下の桁数）
    public const int GramDecimals = 1;

    // 全硬貨のリスト（金額が小さい順）
    public static readonly Coin[] Coins 
        = new[] { new Coin(1, 1), new Coin(5, 3.7), new Coin(10, 4.5),
            new Coin(50, 4.0), new Coin(100, 4.8), new Coin(500, 7) };

    public static readonly Coin Cheapest = Coins[0];
    public static readonly Coin Heaviest = Coins[5];
    public static readonly Coin Lightest = Coins[0];

    private Coin(int val, double gram) : this()
    {
        Value = val;
        Gram = Math.Round(gram, GramDecimals);
    }
        
    // 額面が同額以上のコインを返す
    public Coin[] GetMoreExpensiveOrEqual()
    {
        int index = Array.IndexOf(Coins, this);
        return Coins.Skip(index).ToArray();
    }

}

public class CoinCombination
{
    public IEnumerable<Coin> Coins { get; private set; }
    public double Gram { get; private set; }

    private int mValue = 0;
    public int Value
    {
        get 
        {
            if (mValue == 0) mValue = Coins.Sum((x) => x.Value);
            return mValue; 
        }
    }

    public CoinCombination(IEnumerable<Coin> coins)
    {
        this.Coins = coins;
        Gram = Math.Round(Coins.Sum((x) => x.Gram), Coin.GramDecimals);
    }

    private CoinCombination Prepend(Coin coin)
    {
        return new CoinCombination(new[]{coin}.Concat(Coins));
    }

    private static IEnumerable<CoinCombination> GetCombinations(int combinationSize, Coin cheapest)
    {
        if(combinationSize == 1)
        {
            return cheapest.GetMoreExpensiveOrEqual().Select((x) => new CoinCombination(new[] { x }));
        }
        else
        {
            return cheapest.GetMoreExpensiveOrEqual().SelectMany((x) => 
                GetCombinations(combinationSize - 1, x), (x, y) => y.Prepend(x));
        }
    }

    private static IEnumerable<CoinCombination> GetCombinations(int combinationSize)
    {
        return GetCombinations(combinationSize, Coin.Cheapest);
    }
        
    public static IEnumerable<CoinCombination> GetGramMatched(double gram)
    {
        int minCombinationSize = (int)(gram / Coin.Heaviest.Gram);
        var minCombination = new CoinCombination(Enumerable.Repeat(Coin.Heaviest, minCombinationSize));
        if (gram == minCombination.Gram) yield return minCombination;
            
        int maxCombinationSize = (int)(gram / Coin.Lightest.Gram);

        for (int i = minCombinationSize + 1; i < maxCombinationSize; i++)
            foreach (var item in GetCombinations(i))
                if(gram == item.Gram) yield return item;

        var maxCombination = new CoinCombination(Enumerable.Repeat(Coin.Lightest, maxCombinationSize));
        if (gram == maxCombination.Gram) yield return maxCombination;
    }
    
    public int GetCount(Coin coin)
    {
        return Coins.Count(x => x.Value == coin.Value);
    }
}