## Scienceatlantic.ca

2004 APICS Programming Contest
The 2004 Atlantic Canada programming Contest was held at University New Brunswick St John Friday Oct 15 2004. There were 22 teams of three students from 10 universities in the four Atlantic provinces of Canada. Each team of 3 students was given 6 problems to try to solve in 5 hours using one computer following the rules for the ACM programming contests. c. Minimum Spanning Tree - Arthur Sedgwick f. Set Intersection - Jalal Almhana, Arthur Sedgwick The participating teams came from the following universities: Acadia University, Wolfville N.S. Dalhousie University, Halifax N.S. Memorial University of Newfoundland, St. John's. Mount Allison University, Sackville N.B. St Marys University, Halifax N.S. St Francis Xavier University, Antigonish N.S. University of Prince Edward Island, Charlottetown. University of New Brunswick, Fredericton Campus. University of New Brunswick, St John Campus. Universite de Moncton, Moncton N.B. The top 3 teams from this competition advanced to the next level of competition in Rochester N.Y. Consider the following problem that has recently come up at the McCrafty Fast Food Cor-poration: An efficiency consultant on loan from ENRON has analyzed McCrafty restaurantoperations worldwide and noted the following three universal factors when cashiers givecustomers change from a purchase: 1. Cashiers like to give back as few coins as possible; 2. Customers are willing to accept a lower amount than their actual change if it keeps a 3. The relative strengths of preferences (1) and (2) vary from season to season and from country to country, e.g., some cashiers are lazier than others and some customers arestingier than others.
Given a set C = {c1, c2, . . . , cn} of n coin-values and the amount amt owed a customer, theconsultant has proposed the function a × minC oins(C, ret)) + (ib × (amt − ret)) where ret is the amount returned by the cashier, ia and ib are cashier and customer irritationfactors, respectively, and minCoins(C, x) is the minimum number of coins with values fromthe set C whose values sum to x (note that minCoins(C, x) = 0 if there is no set of coinswith values from C whose values sum to x). For example, given C = {2, 5, 25} and amt = 49, • f (45, 1, 1) = (1 × 5) + (1 × (49 − 45)) = 9; • f (47, 1, 1) = (1 × 6) + (1 × (49 − 47)) = 8; • f (45, 3, 1) = (3 × 5) + (1 × (49 − 45)) = 19; and • f (47, 3, 1) = (3 × 6) + (1 × (49 − 47)) = 20.
The consultant conjectures that if the cashier always returns change equal to the value of retthat minimizes f (), cashier and customer satisfaction will be optimized and the McCraftyCorporation will also have access to a previously underutilized source of revenue.
Given C, amt, ia, and ib, compute a value ret that minimizes function f () specified above. The input will consist of a (3 × i)-line file, i ≥ 1, such that in each group of 3 lines,line 1 gives the number n of coins in C, line 2 contains the n values of the coins in C sortedin ascending order, and line 3 gives the values of amt, ia, and ib, respectively. You mayassume that all input files are formatted correctly.