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

class Program
{
    static void Main(string[] args)
    {
        double targetWeight = 23.7;
        var combinations = CoinCombination.GetCombinations(targetWeight);

        Console.WriteLine("Target Weight(Gram): " + targetWeight);
        Console.WriteLine("Number of Combinations: " + combinations.Count);

        Array.ForEach(Coin.Coins, x => Console.Write((x.Value + "yen").PadLeft(7)));
        Console.WriteLine(" : Total Amount");
        Console.WriteLine(new string('-', 58));
            
        foreach (var c in combinations)
        {
            foreach (var coin in Coin.Coins)
                Console.Write(c.GetCount(coin).ToString().PadLeft(7));
            Console.WriteLine(" : " + c.Value.ToString().PadLeft(12));
        }
    }
}

public struct Coin
{
    public int Value { get; private set; }
    public double Gram { get; private 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) };

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

public class CoinCombination
{
    public List<Coin> Coins { get; private set; }

    // この組み合わせの中の最高額の硬貨。(GetExpandeds参照)
    public Coin MostExpensive 
    { 
        get { return Coins[Coins.Count - 1]; }
    }

    private double mGram;
    public double Gram 
    {
        get { return mGram; }
        private set { mGram = Math.Round(value, Coin.GramDecimals); }
    }

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

    private CoinCombination() { Coins = new List<Coin>(); }

    public CoinCombination(params Coin[] coins) :this()
    {
        Coins.AddRange(coins);
        Gram = Coins.Sum(x => x.Gram);
    }

    // コインを一つ追加したCoinCombinationのリストを返す。
    // MostExpensiveより額面が小さいコインは追加しない。追加後のGramがmaxGramを超えるCoinCombinationは戻り値に含めない。
    private List<CoinCombination> GetExpandeds(double maxGram)
    {
        var ret = new List<CoinCombination>();
        foreach (var coin in MostExpensive.GetMoreExpensiveOrEqual())
        {
            var expanded = new CoinCombination() { Gram = this.Gram + coin.Gram };
            if(expanded.Gram <= maxGram)
            {
                expanded.Coins.AddRange(this.Coins); expanded.Coins.Add(coin);
                ret.Add(expanded);
            }
        }
        return ret;
    }

    // combinationsの要素とそれらに再帰的にコインを追加したものから
    // Gramの値がtargetGramに一致するものを検索しリストにして返す。
    private static List<CoinCombination> GetCombinations(double targetGram, IEnumerable<CoinCombination> combinations)
    {
        var ret = new List<CoinCombination>();
        foreach (var c in combinations)
        {
            if (c.Gram == targetGram)
                ret.Add(c);
            else
                ret.AddRange(GetCombinations(targetGram, c.GetExpandeds(targetGram)));
        }
        return ret;
    }
        
    public static List<CoinCombination> GetCombinations(double targetGram)
    {
        return GetCombinations(targetGram, Coin.Coins.Select(x => new CoinCombination(x)));
    }

    public int GetCount(Coin coin)
    {
        return Coins.Count(x => x.Value == coin.Value);
    }
}