{* 
 * Solution to Problem 2 (Pascal)
 * 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
 *}

program problem2(input,output);

const

{* this is the sqaure root of the maximum coin value *}
   MAX_COIN_SQRT = 9;

{* the minimum amount the user can input ; should be positive }
   MIN_AMT=0;

{* the maximum the user can input; should be larger than MIN_AMT *}
   MAX_AMT=300;

var
{* the amount to be payed *}
amount :integer;

{* 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.
 *}
function countWays(amount, max : integer ) : integer;
var
{* the number of ways to pay the amount *}
ways	   :integer;
{* holds the face value of a coin *}
coinVal :integer;
{* holds the square root of the current coin *}
   coinSqrt : integer;
begin

   ways := 0;
   
  {* 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 then
  begin
     countWays := 1;
  end
  else
  begin
     
     for coinSqrt := max downto 1 do
     begin
	coinVal := coinSqrt * coinSqrt;
	
	if  coinVal <= amount then
	begin
	   {replace old max with current coin value}
	   ways := ways + countWays(amount - coinVal, coinSqrt);
	end;
     end;
     
     countWays := ways;
  end;
end;
   

begin

   
   Writeln("What is the amount you wish to pay in Silverland coins:");
   Readln(amount);

  if (( amount < MIN_AMT) or  ( amount > MAX_AMT)) then
  begin
     Writeln("That is not a valid amount");
  end
  else
  begin
     Write("There are ");
     Write(countWays(amount, MAX_COIN_SQRT));
     Write(" ways to pay that amount.")
  end;

end.