Untitled

  public class VendingMachine
  {
      private readonly SortedDictionary<int, int> _state;
      private readonly object _sync = new object();

      public VendingMachine()
      {
          _state = new SortedDictionary<int, int>
          {
              {50, 0},
              {100, 0},
              {500, 0},
              {1000, 0},
              {5000, 0}
          };
      }

      public void PushMoney(int nominal, int count)
      {
          lock (_sync)
          {
              var isValidNominal = _state.ContainsKey(nominal);
              if (!isValidNominal)
              {
                  throw new ArgumentException("invalid nominal", nameof(nominal));
              }

              _state[nominal] += count;
          }
      }

      /// <summary>
      /// Return banknotes 
      /// </summary>
      /// <param name="amount"></param>
      /// <returns>map nominal->count</returns>
      public IReadOnlyDictionary<int, int> PullMoney(int amount)
      {
          lock (_sync)
          {
              var min = _state.Min(x => x.Key);
              if (amount % min > 0)
              {
                  throw new ArgumentException("invalid amount", nameof(amount));
              }

              var balance = _state.Sum(x => x.Key * x.Value);
              if (amount > balance)
              {
                  throw new InvalidOperationException("insufficient balance");
              }

              // map nominal->count 
              var result = new Dictionary<int, int>();
              var keys = _state.Keys.ToArray();
              for (var i = keys.Length - 1; i >= 0 && amount > 0; i--)
              {
                  var nominal = keys[i];
                  var count = _state[nominal];
                  if (count > 0 && nominal <= amount)
                  {
                      var candidateCount = amount / nominal;
                      var withdrawalCount = Math.Min(candidateCount, count);

                      result.Add(nominal, withdrawalCount);

                      amount = -withdrawalCount * nominal;
                  }
              }

              if (amount > 0)
              {
                  throw new InvalidOperationException("unavailable nominal count");
              }

              foreach (var (nominal, count) in result)
              {
                  _state[nominal] -= count;
              }

              return result;
          }
      }
  }