fork download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. class Program
  6. {
  7.     static void Main(string[] args)
  8.     {
  9.         double targetWeight = 23.7;
  10.  
  11.         Array.ForEach(Coin.Coins, x => Console.Write((x.Value + "yen").PadLeft(6)));
  12.         Console.WriteLine(" : Total Amount");
  13.         Console.WriteLine(new string('-', 52));
  14.  
  15.         var combinations = CoinCombination.GetGramMatched(targetWeight);
  16.         int count = 0;
  17.         foreach (var c in combinations)
  18.         {
  19.             foreach (var coin in Coin.Coins)
  20.                 Console.Write(c.GetCount(coin).ToString().PadLeft(6));
  21.             Console.WriteLine(" : " + c.Value.ToString().PadLeft(12));
  22.             count++;
  23.         }
  24.         Console.WriteLine(new string('-', 52));
  25.  
  26.         Console.WriteLine("Target Weight(Gram): " + targetWeight);
  27.         Console.WriteLine("Number of Combinations: " + count);
  28.         Console.ReadLine();
  29.     }
  30. }
  31.  
  32. public struct Coin
  33. {
  34.     public int Value { get; private set; }
  35.     public double Gram { get; set; }
  36.  
  37.     // Gramの有効数字（小数点以下の桁数）
  38.     public const int GramDecimals = 1;
  39.  
  40.     // 全硬貨のリスト（金額が小さい順）
  41.     public static readonly Coin[] Coins 
  42.         = new[] { new Coin(1, 1), new Coin(5, 3.7), new Coin(10, 4.5),
  43.             new Coin(50, 4.0), new Coin(100, 4.8), new Coin(500, 7) };
  44.  
  45.     public static readonly Coin Cheapest = Coins[0];
  46.     public static readonly Coin Heaviest = Coins[5];
  47.     public static readonly Coin Lightest = Coins[0];
  48.  
  49.     private Coin(int val, double gram) : this()
  50.     {
  51.         Value = val;
  52.         Gram = Math.Round(gram, GramDecimals);
  53.     }
  54.  
  55.     // 額面が同額以上のコインを返す
  56.     public Coin[] GetMoreExpensiveOrEqual()
  57.     {
  58.         int index = Array.IndexOf(Coins, this);
  59.         return Coins.Skip(index).ToArray();
  60.     }
  61.  
  62. }
  63.  
  64. public class CoinCombination
  65. {
  66.     public IEnumerable<Coin> Coins { get; private set; }
  67.     public double Gram { get; private set; }
  68.  
  69.     private int mValue = 0;
  70.     public int Value
  71.     {
  72.         get 
  73.         {
  74.             if (mValue == 0) mValue = Coins.Sum((x) => x.Value);
  75.             return mValue; 
  76.         }
  77.     }
  78.  
  79.     public CoinCombination(IEnumerable<Coin> coins)
  80.     {
  81.         this.Coins = coins;
  82.         Gram = Math.Round(Coins.Sum((x) => x.Gram), Coin.GramDecimals);
  83.     }
  84.  
  85.     private CoinCombination Prepend(Coin coin)
  86.     {
  87.         return new CoinCombination(new[]{coin}.Concat(Coins));
  88.     }
  89.  
  90.     private static IEnumerable<CoinCombination> GetCombinations(int combinationSize, Coin cheapest)
  91.     {
  92.         if(combinationSize == 1)
  93.         {
  94.             return cheapest.GetMoreExpensiveOrEqual().Select((x) => new CoinCombination(new[] { x }));
  95.         }
  96.         else
  97.         {
  98.             return cheapest.GetMoreExpensiveOrEqual().SelectMany((x) => 
  99.                 GetCombinations(combinationSize - 1, x), (x, y) => y.Prepend(x));
  100.         }
  101.     }
  102.  
  103.     private static IEnumerable<CoinCombination> GetCombinations(int combinationSize)
  104.     {
  105.         return GetCombinations(combinationSize, Coin.Cheapest);
  106.     }
  107.  
  108.     public static IEnumerable<CoinCombination> GetGramMatched(double gram)
  109.     {
  110.         int minCombinationSize = (int)(gram / Coin.Heaviest.Gram);
  111.         var minCombination = new CoinCombination(Enumerable.Repeat(Coin.Heaviest, minCombinationSize));
  112.         if (gram == minCombination.Gram) yield return minCombination;
  113.  
  114.         int maxCombinationSize = (int)(gram / Coin.Lightest.Gram);
  115.  
  116.         for (int i = minCombinationSize + 1; i < maxCombinationSize; i++)
  117.             foreach (var item in GetCombinations(i))
  118.                 if(gram == item.Gram) yield return item;
  119.  
  120.         var maxCombination = new CoinCombination(Enumerable.Repeat(Coin.Lightest, maxCombinationSize));
  121.         if (gram == maxCombination.Gram) yield return maxCombination;
  122.     }
  123.  
  124.     public int GetCount(Coin coin)
  125.     {
  126.         return Coins.Count(x => x.Value == coin.Value);
  127.     }
  128. }
Time limit exceeded #stdin #stdout 5s 36872KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
  1yen  5yen 10yen 50yen100yen500yen : Total Amount
----------------------------------------------------
     0     2     1     0     1     1 :          620
     0     1     2     1     0     1 :          575
     0     0     1     0     4     0 :          410
     2     1     0     1     0     2 :         1057
     1     1     0     3     0     1 :          656
     0     1     0     5     0     0 :          255
     2     1     4     0     0     0 :           47
     4     1     2     0     0     1 :          529
     3     3     0     0     2     0 :          218
     3     2     1     1     1     0 :          173
     3     1     2     2     0     0 :          128
     6     1     0     0     0     2 :         1011
     5     1     0     2     0     1 :          610
     4     1     0     4     0     0 :          209
     7     2     1     0     1     0 :          127
     7     1     2     1     0     0 :           82
     9     1     0     1     0     1 :          564
     8     1     0     3     0     0 :          163
    11     1     2     0     0     0 :           36
    13     1     0     0     0     1 :          518
    12     1     0     2     0     0 :          117
https://ideone.com/gfMQ0l
language:
C# (gmcs 5.20.1)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!