using System.Collections.Generic;
var moneys = new int[] {1, 1840, 100000, 1680, 15, 37, 3, 500000000};
var state = new Dictionary<int, int>();
var nominals = new List<int>(state.Keys);
var combinations = new List<Combination>();
for(var start = 0; start < state.Keys.Count; start++)
for(var end = 0; end < state.Keys.Count; end++)
var combination = GetCombination(start, end, nominals);
combinations.Add(combination);
combinations = combinations.OrderByDescending(i => i.Sum).ToList();
foreach(var money in moneys)
var result = GiveMoney(money, combinations, state);
foreach(var transaction in result)
transaction.Validate(state);
transaction.SetWeight(state);
var validTransactions = result.Where(i => i.Valid == true);
if(validTransactions.Count() > 0)
var selectedTransaction = validTransactions.OrderBy(i => i.Weight).First();
selectedTransaction.Print();
state = RunTransaction(state, selectedTransaction);
Console.Write("Can not run transaction for requested ");
Console.WriteLine(money);
public Dictionary<int, int> Parameters {get; set;}
public double Weight {get; set;}
public bool Valid {get; set;}
public bool Validate(Dictionary<int, int> state)
foreach(var key in Parameters.Keys)
if(!state.ContainsKey(key))
if(state[key] - Parameters[key] < 0)
public void SetWeight(Dictionary<int, int> state)
var newState = new Dictionary<int, int>();
foreach(var key in Parameters.Keys)
newState[key] = state[key] - Parameters[key];
foreach(var key in newState.Keys)
sqr += (double) ((newState[key] - state[key])*(newState[key] - state[key]));
foreach(var key in Parameters.Keys)
Console.Write(Parameters[key]);
Console.Write("SquaresMin=");
public int Sum {get; set;}
public List<int> Nominals{get; set;}
foreach(var nominal in Nominals)
public Dictionary<int, int> RunTransaction(Dictionary<int, int> state, Transaction transaction)
var newState = new Dictionary<int, int>();
foreach(var key in state.Keys)
if(transaction.Parameters.ContainsKey(key))
newState[key] = state[key] - transaction.Parameters[key];
newState[key] = state[key];
public Transaction Merge(Transaction left, Transaction right)
var result = new Transaction();
var parameters = new Dictionary<int, int>();
result.Parameters = parameters;
var transactions = new List<Transaction>();
foreach(var transaction in transactions)
foreach(var key in transaction.Parameters.Keys)
if(result.Parameters.ContainsKey(key))
result.Parameters[key] += transaction.Parameters[key];
result.Parameters[key] = transaction.Parameters[key];
public Combination GetCombination(int start, int end, List<int> list)
var combination = new Combination();
var nominals = new List<int>();
for(var i = start; i <= end; i++)
combination.Nominals = nominals;
public List<Transaction> GiveMoney(int money, List<Combination> combinations, Dictionary<int, int> state)
var transactions = new List<Transaction>();
foreach(var combination in combinations)
var transaction = new Transaction();
var parameters = new Dictionary<int, int>();
if(money >= combination.Sum)
var ostatok = (int)(money % combination.Sum);
var chastnoye = (int) ((money - ostatok) / combination.Sum);
foreach(var nominal in combination.Nominals)
parameters[nominal] = chastnoye;
transaction.Parameters = parameters;
var childs = GiveMoney(ostatok, combinations, state);
foreach(var child in childs)
transactions.Add(Merge(transaction, child));
transactions.Add(transaction);