Pages

Thursday, September 17, 2015

Money Changing Problem (KICTM UiTM Jasin 2015)

A small local shop is having a problem because the assistants find it hard to work out how much change to give to customers. You have been asked to help them by writing a program that does all the work! Notes and coins available are as follows:

Notes: $20, $10, $5, $2, $1.
Coins: 50c, 20c, 10c, 5c.

As the smallest coin available is 5c, the cost of the purchase may need to be rounded to the nearest 5c, using the so-called Swedish rounding method. The rules for rounding are as follows:

1 or 2 cents = rounded down to 0.
3 or 4 cents = rounded up to 5.
6 or 7 cents = rounded down to 5.
8 or 9 cents = rounded up to 10.

The program must work out the change required and specify the notes and coins to use. In each case, the smallest possible number of notes and coins must be used.

Input 
Each line of input will represent a single transaction, and will contain 2 decimal numbers in the range 0.05 to 1000.00, each with two digits after the decimal point, and separated by a single space. The first number is the cost of a purchase, the second the amount the customer offers at the till. As mentioned, the cost of the purchase may need to be rounded, and, of course, the amount offered by the customer is a multiple of 5 cents. A line consisting of two 0.00 numbers marks the end of the input.

Output 
Your program must output one line for each transaction. Where the amount of money offered by the customer is not enough to cover the rounded purchase price, your program must output

Not enough money offered.

Where the amount of money offered by the customer is exactly the rounded purchase price, your program must output

Exact amount.

In all other cases output the sequence describing the change. Each sequence item starts with a note or coin value in the format described earlier (e.g., $2 or 10c), followed by a multiplication sign (i.e., an asterisk, `*') and ends with a repetition count (a number >= 1). Items are listed in order of decreasing values and are separated by single spaces.

Sample Input 

20.03 20.00
20.07 20.05
20.08 25.00
0.09 0.10
0.00 0.00

Sample Output 

Not enough money offered.
Exact amount.
$2*2 50c*1 20c*2
Exact amount.



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
import java.util.*;
import java.lang.*;
import java.math.*;
import java.text.*;

public class Q5{
   public static void main(String[] args){
      Scanner scan = new Scanner(System.in);
      
      DecimalFormat df = new DecimalFormat("0.00");
      String line = System.getProperty("line.separator");
      scan.useDelimiter(line);
      
      while (true){
         String get = scan.next();
         String[] init = get.split(" ");
         
         if(get.equals("0.00 0.00"))
            break;
         
         int bil = Integer.parseInt(""+init[0].charAt(init[0].length()-1));
         
         if(bil == 1 || bil == 2)
            init[0] = init[0].substring(0,init[0].length()-1)+"0";
         else if(bil ==3 || bil == 4)
            init[0] = init[0].substring(0,init[0].length()-1)+"5";
         else if(bil ==6 || bil == 7)
            init[0] = init[0].substring(0,init[0].length()-1)+"5";
         else if(bil ==8 || bil == 9){
            init[0] = df.format(Float.parseFloat(init[0])+0.1);
            init[0] = init[0].substring(0,init[0].length()-1)+"0";
         }

         if(Float.parseFloat(init[0])>Float.parseFloat(init[1]))
            System.out.println("Not enough money offered.");
         else if(init[0].equals(init[1]))
            System.out.println("Exact amount.");
         else{
            String total = df.format(Float.parseFloat(init[1]) - Float.parseFloat(init[0]));
            System.out.println(findMin(Float.parseFloat(total)));
         }
      }  
   }
   
   public static String findMin(float total){
      float n = total*100;
      int [] sets = new int[]{5,10,20,50,100,200,500,1000,2000};
      List<String> list = new ArrayList<String>();
      int counta=0;
      
      while(n>0){
         int max = sets[0]; 
         //review my blog title "minumum coin change"  
         //find list of minumum coin change (sorted coins list)
         for(int x=sets.length-1;x>=0;x--){
            if(sets[x]<=n){
               max = sets[x];
               break;
            }
         }
         
         if(max>=100){
            //convert cents to dollar
            int rev = max/100;
            list.add("$"+rev);
         }
         else
            list.add(max+"c");

         n=n-max;
      }
      
      StringBuilder str = new StringBuilder();

      Set<String> set = new HashSet<String>(list); 
      String []newstr = new String[set.size()];
      set.toArray(newstr);
      
      for(int x=0;x<newstr.length;x++){
          for(int y=0;y<list.size();y++){
             if(newstr[x].equals(list.get(y))){
                counta++;
             }
          }
          str.append(newstr[x]+"*"+counta+" ");
          counta=0;
      }      
      return str.toString();
   }
   
   
}

No comments:

Post a Comment