algorithms

programing in c language

Shopping is FUN Kang Ji Sung very loves shopping. Whenever shops have a discount event, he completely goes crazy and wants to buy all items in the shops. You are his best friend; you cannot stop him from shopping but you can give him a shopping strategy to save his money. Today, a shop offers a very good deal "Buy 3 only pay 2 with a rule that in one bill only the cheapest ones get free. Your job is to help him find the maximum discount he can get. Example: - Your friend wants to buy 7 items, costing 350000, 14400000, W300000 ?100000, \ 150000, ?200000, and \250000. -If he buys all items in one bill, he gets 2 free items which are the cheapest ones of W100000 and 150000. Consequently, he gets the discount of 250000 and must pay ?1500000 If he buys the items separately, he may get a bigger discount. For instance, he separates the items in three bills as follow The first bills: 3 items ?400000, ?300000, and \\250000 ? \250000 discount. o The second bill: 2 items W350000, 200000 and W100000100000 discount. o The third bill: 1 item 150000no discount. o Eventually, he gets the total discount of 350000 and must pay #1400000 Input is read from the text file shopping.inp consisting of The first line is the number of items he buys The second line is the list of prices of items Output is written to the text file shopping.out consisting of ONLY ONE NUMBER which is the maximum discount he can get. Example: shopping.inp shopping.out 400000 100000 400000 200000 350000 300000 250000