import SimpleOutput;

/**
 * A very simple computation of the minimum number of stamps 
 * needed to total a particular price.  Based on Stamps.java,
 * given in HW3 of CSC152 2000S.  This extended version reports
 * on the number of function calls and uses a table to improve
 * the running time.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of March 2000
 */
public class NewerStamps 
{
  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /** The number of recursive calls executed. */
  protected int numCalls;
  
  /** 
   * An array holding all the stamp values knows.  Has -1 in
   * each cell as a default.
   */
  protected int[] minStamps;
  
  // +---------+-------------------------------------------------
  // | Helpers |
  // +---------+

  /**
   * Compute the minimum number of stamps that exactly
   * totals val cents.  Puts the values of the stamps in
   * stampsToBuy, starting at index stampNum.
   * Pre: (1) val >= 0
   *      (2) All stamps values are positive.
   *      (3) It is possible to combine stamps for any value.
   *      (4) It requires no more than MAXSTAMPS stamps.
   * Post: Returns N such that it is possible to buy N stamps
   *   for exactly val and it is not possible to buy M < N 
   *   stamps for exactly val.
   */
  public int minimumStamps(int val, int[] stampValues)
  {
    // Increment the number of calls, since we're keeping track
    ++numCalls;
    // Preparation: Make sure that minStamps is defined.  This should
    // only be done once overall.
    if ((this.minStamps == null) || (this.minStamps.length <= val)) {
      this.minStamps = new int[val+1];
      for (int i = 1; i <= val; i++)
        minStamps[i] = -1;
      minStamps[0] = 0;
    }
    // Special case: minStamps[val] is not yet set.
    if (minStamps[val] < 0) {
      int i = 0; // An index into stampValues
      int guess; // Our best guess so far as to the minimum.
      int nextGuess;  // Another guess to try
      int buyThisTime; // The stamp to buy in this round.
  
      // Find the first stamp that's still worth buying.
      while (stampValues[i] > val)
        i++;
  
      // We might buy that stamp.
      buyThisTime = stampValues[i];
      guess = 1 + minimumStamps(val-stampValues[i], stampValues);
  
      // But we might also buy other stamps.
      for (i = i+1; i < stampValues.length; i++) {
        if (stampValues[i] <= val) {
          nextGuess =
            1 + minimumStamps(val-stampValues[i], stampValues);
          if (nextGuess < guess) {
            buyThisTime = stampValues[i];
            guess = nextGuess;
          } // if it's a better guess
        } // if the stamp is worth buying.
      } // for
      
      // Okay, we have a final solution
      minStamps[val] = guess;
    } // Special case
    
    // Okay, the array is now filled in!
    return minStamps[val];
  } // minimumStamps(int, int[])

  // +------+----------------------------------------------------
  // | Main |
  // +------+

  public static void main(String[] args) {
    int val = 0;
    SimpleOutput out = new SimpleOutput();   
    NewerStamps helper = new NewerStamps();
    // Set up the array of stamp values.
    int[] stamps = { 1, 5, 20, 33, 50 };

    // Sanity check.
    if (args.length != 1) {
      out.println("Usage: java Stamps value");
      System.exit(1);
    }
    // Get the value.
    try { val = (new Integer(args[0])).intValue(); }
    catch (NumberFormatException e) {
      out.println("The value must be an integer.");
      System.exit(2);
    } // catch
    // Verify that the preconditions are met.
    if (val < 0) {
      out.println("The value must be positive.");
      System.exit(3);
    } // if (val < 0)
    // Compute away!
    helper.numCalls = 0;
    int numStamps = helper.minimumStamps(val, stamps);
    if (numStamps == 0)
      out.println("You need no stamps to make no cents.");
    else if (numStamps == 1)
      out.println("You need one stamp to make " + val + " cents.");
    else
      out.println("You need " + numStamps + " stamps to make " 
                  + val + " cents.");
    out.println("That used " + helper.numCalls + " recursive calls.");
  } // main(String[])

} // class NewerStamps