#include <stdlib.h>
#include <iostream.h>
#include <assert.h>

struct CoinsHold
{
  int Nickelhold;
  int Dimehold;
  int Quarterhold;
} TheHold;

struct CoinsQuantity
{
  int Quarters;
  int Dimes;
  int Nickels;
} CoinsCount;

/****************************************************************************/
void SetCoinsQuantity(int n, int d, int q)
{
  CoinsCount.Quarters = q;
  CoinsCount.Dimes = d;
  CoinsCount.Nickels = n;
}

/****************************************************************************/
int FindChange(int Value, CoinsHold& CoinsHoldObj)
{
  int ntried;
  int dtried;
  int qtried;
  int n;
  int d;
  int q;
  int ChangeAmt;
  int nqty;
  int dqty;
  int qqty;
  int nmax;
  int dmax;
  int qmax;

  ChangeAmt = 0;
  nqty = CoinsHoldObj.Nickelhold;
  dqty = CoinsHoldObj.Dimehold;
  qqty = CoinsHoldObj.Quarterhold;

  if (nqty >= Value)
    nmax = Value;
  else
    nmax = nqty * 5;

  if (dqty >= Value)
    dmax = Value;
  else
    dmax = dqty * 10;

  if (qqty >= Value)
    qmax = Value;
  else
    qmax = qqty * 25;

  if (nmax + dmax + qmax < Value)
    return 0;

  n = 0;
  d = 0;
  q = 0;
  ntried = 0;
  dtried = 0;
  qtried = 0;

  while (1)
  {
    if (!ntried)
    {
      if (n)
	ChangeAmt += 5;

      qtried = 0;
      dtried = 0;
      ntried = ChangeAmt > Value || n >= nmax;
    }

    if (ChangeAmt == Value)
    {
      SetCoinsQuantity(n / 5, d / 10, q / 25);
      return 1;
    }
    else if (ntried && dtried && qtried)
    {
      ChangeAmt -= n;
      n = 0;
      break;
    }

    d = 0;
    while (1)
    {
      if (!dtried)
      {
	if (d)
	  ChangeAmt += 10;

	qtried = 0;
	dtried = ChangeAmt > Value || d >= dmax;
      }

      if (ChangeAmt == Value)
      {
	SetCoinsQuantity(n / 5, d / 10, q / 25);
	return 1;
      }
      else if (dtried && qtried)
      {
	ChangeAmt -= d;
	d = 0;
	break;
      }

      q = 0;
      while (1)
      {
	if (!qtried)
	{
	  if (q)
	    ChangeAmt += 25;

	  qtried = ChangeAmt > Value || q >= qmax;
	}

	if (ChangeAmt == Value)
	{
	  SetCoinsQuantity(n / 5, d / 10, q / 25);
	  return 1;
	}
	else if (qtried)
	{
	  ChangeAmt -= q;
	  q = 0;
	  break;
	}

	if (!qtried)
	  q += 25;
      }

      if (!dtried)
	d += 10;
    }

    if (!ntried)
      n += 5;
  }

  return 0;
}

/****************************************************************************/
#if defined(__TURBOC__) | defined(__DJGPP__)
  #include <conio.h>
#endif
void main()
{
  int x, y, z, i;
  int a, b, c;

#if defined(__TURBOC__) | defined(__DJGPP__)
  clrscr();
#endif

  for (x = 0; x < 10; ++x)
    for (y = 0; y < 10; ++y)
      for (z = 0; z < 10; ++z)
      {
	TheHold.Nickelhold = x;
	TheHold.Dimehold = y;
	TheHold.Quarterhold = z;

	for (i = 0; i <= 400; i += 5)
	  if (FindChange(i, TheHold))
	  {
	    assert(i == CoinsCount.Nickels * 5 + CoinsCount.Dimes * 10 + CoinsCount.Quarters * 25);
	    assert(CoinsCount.Nickels <= TheHold.Nickelhold &&
		   CoinsCount.Dimes <= TheHold.Dimehold &&
		   CoinsCount.Quarters <= TheHold.Quarterhold);
	  }
	  else
	  {
	    for (a = 0; a <= TheHold.Nickelhold; ++a)
	      for (b = 0; b <= TheHold.Dimehold; ++b)
		for (c = 0; c <= TheHold.Quarterhold; ++c)
		  if (a * 5 + b * 10 + c * 25 == i)
		  {
		    cout <<"Failure:"
			 <<" i = " <<i
			 <<" nhold = " <<TheHold.Nickelhold
			 <<" dhold = " <<TheHold.Dimehold
			 <<" qhold = " <<TheHold.Quarterhold <<endl
			 <<" a = " <<a <<" b = " <<b <<" c = " <<c <<endl;
		    exit(-1);
		  }
	  }
      }
}

/****************************************************************************/