/* 
 * Solution to Problem 2 (C++)
 * 11th Annual CS Programming Contest
 * WCU Dept of Math and CS
 * Copyright 2000 , All Rights Reserved
 *
 * Problem Statement:
 * A certain region uses coins of values 1,4,9,16,...,81 .
 * For a certain amount of money there are many ways
 * to pay that amount in coins.  This program computes the number
 * of ways to pay a user-input amount in these coins.
 * Per the probelm statement, the amount to be paid is 
 * tested to ensure that it is in the range 1 <= x <= 300
 */

#include <iostream.h>

/* this is the sqaure root of the maximum coin value */
#define MAX_COIN_SQRT 9

/* the minimum amount the user can input ; should be positive */
#define MIN_AMT 0

/* the maximum the user can input; should be larger than MIN_AMT */
#define MAX_AMT 300

/* This function recursively computes the
 * number of ways to pay a certain amount, 
 * based on the largetst coin available.
 *
 * Because once a coin of size x is used, no
 * coin of size >= x can ever be used, this
 * algorithm cannot count mere permutations of the same
 * coins as different ways of paying the amount.
 */
int countWays(int amount, int max)
{

  /* Base case: we can pay one credit with a single coin.
   * To pay zero or fewer credits, there is only one possible 
   * sequence, which is the empty sequence.
   */

  if ( amount <= 1)
    return 1;

  /* the number of ways to pay the amount */
  int ways = 0;

  /* holds the face value of a coin */
  int coinVal;

  for(int coinSqrt = max; coinSqrt > 0; coinSqrt--)
  {
    coinVal = coinSqrt * coinSqrt;

    if ( coinVal <= amount)
                            //replace old max with current coin value
      ways += countWays(amount - coinVal, coinSqrt); 
  }

  return ways;
}


int main()
{

  /* the amount to be payed */
  int amount;

  cout << "What is the amount you wish to pay in Silverland coins:";
  cin >> amount;
  if ( (amount < MIN_AMT) || (amount > MAX_AMT))
  {
    cout << "That is not a valid amount" << endl;
  } else {
    cout << "There are " 
         << countWays(amount, MAX_COIN_SQRT) 
         << " ways to pay" << endl;
  }

}