import SimpleOutput;

/**
 * A very simple iterative computation of the minimum
 * number of stamps needed to total a particular price.  
 * Based on a recursive version given as part of HW3 of
 * CSC152 2000S and rewritten for the answer key.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of March 2000
 */
public class IterativeStamps 
{
  // +---------+-------------------------------------------------
  // | 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 static int minimumStamps(int val, int[] stampValues)
  {
    // A friendly helper array.
    int[] minStamps = new int[val+1];
    minStamps[0] = 0;
    // Step through the possible values, setting the result as we go.
    for (int partialValue = 1; partialValue <= val; partialValue++) {
      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] > partialValue)
        i++;
  
      // We might buy that stamp.
      buyThisTime = stampValues[i];
      guess = 1 + minStamps[partialValue-stampValues[i]];
  
      // But we might also buy other stamps.
      for (i = i+1; i < stampValues.length; i++) {
        if (stampValues[i] <= partialValue) {
          nextGuess =
            1 + minStamps[partialValue-stampValues[i]];
          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[partialValue] = guess;
    } // for each posible value
    
    // 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();   
    // 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!
    int numStamps = 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.");
  } // main(String[])

} // class IterativeStamps