CareerCup

A credit card company allows merchants to use their Point-of-sale (POS) terminal to accept payments. It wishes to charge merchants for every transaction that happens through thier POS terminal. Here are some charging rules that it has come up with:

Transactions are charged 2.0% of transaction amount if amount is less than 5000.00
Transactions are charged 1.5% of transaction amount if amount is between 5000.00 and 9999.99 (both inclusive)
Transactions are charged 1.0% of transaction amount if amount is equal to or above 10000.00
If merchant has already done transactions worth 50000.00 in a month, then rest of transactions of that month are charged at 0.5%
Every Month - two transactions of amount less than or equal to Rs. 5000.00 are free
Charges are rounded to nearest higher Rupee (Eg: 9.23 is rounded to 10.00)
Please develop a program to compute the charges for given inputs.

Your input will be in the following format. First Line: number of records follows, say N Next N Lines - Transaction data in the order - Transaction Date, Merchant Name, Amount

15
2014-06-25,XYZ Retail,10000.00
2014-07-01,XYZ Retail,10000.00
2014-07-01,ABC Retail,1000.00
2014-07-02,ABC Retail,3999.00
2014-07-02,ABC Retail,2000.00
2014-07-03,ABC Retail,10000.00
2014-07-15,ABC Retail,6530.00
2014-07-15,XYZ Retail,500.00
2014-07-18,ABC Retail,9750.00
2014-07-18,XYZ Retail,35000.00
2014-07-18,XYZ Retail,500.00
2014-07-18,XYZ Retail,5000.00
2014-07-18,XYZ Retail,5000.00
2014-08-02,XYZ Retail,10000.00
2014-08-02,XYZ Retail,1000.00
Transactions must be read and processed in the order given, else output will not match. Do not try to sort the transactions.

Output (Charges for each transaction on separate line)

100.00
100.00
0.00
0.00
40.00
100.00
98.00
0.00
147.00
350.00
0.00
75.00
25.00
100.00
0.00
Sample Input (Plaintext Link)
15
2014-06-25,XYZ Retail,10000.00
2014-07-01,XYZ Retail,10000.00
2014-07-01,ABC Retail,1000.00
2014-07-02,ABC Retail,3999.00
2014-07-02,ABC Retail,2000.00
2014-07-03,ABC Retail,10000.00
2014-07-15,ABC Retail,6530.00
2014-07-15,XYZ Retail,500.00
2014-07-18,ABC Retail,9750.00
2014-07-18,XYZ Retail,35000.00
2014-07-18,XYZ Retail,500.00
2014-07-18,XYZ Retail,5000.00
2014-07-18,XYZ Retail,5000.00
2014-08-02,XYZ Retail,10000.00
2014-08-02,XYZ Retail,1000.00
Sample Output (Plaintext Link)
100.00
100.00
0.00
0.00
40.00
100.00
98.00
0.00
147.00
350.00
0.00
75.00
25.00
100.00
0.00
Explanation
100.00 // Rule 3 applied
100.00 // Rule 3 applied
0.00 // Rule 5 applied (ABC Retail) for the month of July
0.00 // Rule 5 applied (ABC Retail) for the month of July
40.00 //Rule 1 & 6 applied
100.00 // Rule 3 applied
98.00 // Rule 2 & 6 applied
0.00 // Rule 5 applied (XYZ Retail) for the month of July
147.00 // Rule 2 & 6 applied
350.00 //Rule 3 applied
0.00 // Rule 5 applied (XYZ Retail) for the month of July
75.00 // Rule 2 applied
25.00 // Rule 4 applied
100.00 // Rule 3 applied
0.00 // Rule 5 applied (XYZ retail) - for the month of Augus

There is an sorted array suppose 10 20 30 40 50 60 70 80 90. If we rotate it n times(suppose n = 3 in my case). The array will be 70 80 90 10 20 30 40 50 60. The total no of values which are not in right position 3(in this case which are 70 80 90) so we have to make a generalized solution. I was able to answer this in O(n) but he wants something which is lesser than O(n).