Programming Problem

#1. 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 shopper find the maximum discount he can get. Example: - Your friend wants to buy 7 items, costing $350000, $400000, $300000, $100000, $150000, $200000, and $250000. - If he buys all items in one bill, he gets 2 free items which are the cheapest ones of $100000 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: o The first bills: 3 items $400000, $300000, and $250000 -> $250000 discount. o The second bill: 3 items $350000, $200000 and $100000 -> $100000 discount. o The third bill: 1 item $150000 -> no discount. o Eventually, he gets the total discount of $350000 and must pay $1400000. Input is read from the text file [login to view URL] 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 [login to view URL] consisting of ONLY ONE NUMBER which is the maximum discount he can get. [Example]: [login to view URL] [login to view URL] 6 100000 400000 200000 350000 300000 250000 400000 Limitation: - 1 ≤ number of items he buys ≤ 200000 - 1 ≤ the cost of an item ≤ 1000000 - Processing time of the proposed algorithm ≤ 1 second The output file only has one value - The main function must follow the template: int main(int argc, const char* argv[]) { //content … return 0; } - The extension of the input file of the programming problem is “inp” (ex:[login to view URL]), NOT “[login to view URL]” (ex: [login to view URL]) - Sample code for writing to a text file: #include <stdio.h> int main() { int num; FILE *fptr; fptr = fopen("[login to view URL]","w"); printf("Enter num: "); scanf("%d",&num); fprintf(fptr,"%d",num); fclose(fptr); return 0; }