********************************************************************** GOLD PROBLEMS ********************************************************************** Two problems numbered 1 through 2 ********************************************************************** Problem 1: Making Money [Traditional, 2009] FJ has gone into the curio business, buying and selling knickknacks like cow Christmas tree ornaments. He knows he will sell every single curio he can stock from a catalog of N (1 <= N <= 100) different cow curios, and he can buy as many of each kind of curio as his heart desires. He has only M (1 <= M <= 100,000) money to invest but wants to maximize his profit (which has a slightly unusual definition) at the end of his first year in business. Curio type i costs C_i (1 <= C_i <= 100,000) money to purchase and yields R_i (1 <= R_i <= 100,000) revenue for each curio sold (a profit of R_i-C_i). FJ can mix and match the curios he sells in any way he wishes. He need not spend all his money when purchasing curios. What is the greatest amount of total profit (profit = initial_cash - all_costs + all_sales) FJ can have at the end of his first year? This number is guaranteed to be less than 1,000,000,000. Consider the situation when FJ has just 3 kinds of curios and starts with M=17. Below are the cost and revenue numbers for each curio: Curio Cost Revenue # C_i R_i 1 2 4 2 5 6 3 3 7 In this case, FJ should purchase 5 curios of type 3 for 15 money and 1 more curio of type 1 for 2 money, a total of 17 money. His profit will be 5 * (7-3) + 1 * (4-2) = 5*4 + 1*2 = 22 money. He can do no better than this given the cost and revenue structure. NOTE: The second test case is challenging -- but our answer is correct. PROBLEM NAME: mkmoney INPUT FORMAT: * Line 1: Two space-separated integers: N and M * Lines 2..N+1: Line i+1 contains two space-separated integers: C_i and R_i SAMPLE INPUT (file mkmoney.in): 3 17 2 4 5 6 3 7 OUTPUT FORMAT: * Line 1: The maximum profit FJ can generate given the costs and revenues SAMPLE OUTPUT (file mkmoney.out): 22 ********************************************************************** Problem 2: Soda Machine [Neal Wu, 2008] To meet the ever-growing demands of his N (1 <= N <= 50,000) cows, Farmer John has bought them a new soda machine. He wants to figure out the perfect place to install the machine. The field in which the cows graze can be represented as a one-dimensional number line. Cow i grazes in the range A_i..B_i (1 <= A_i <= B_i; A_i <= B_i <= 1,000,000,000) (a range that includes its endpoints), and FJ can place the soda machine at any integer point in the range 1..1,000,000,000. Since cows are extremely lazy and try to move as little as possible, each cow would like to have the soda machine installed within her grazing range. Sadly, it is not always possible to satisfy every cow's desires. Thus FJ would like to know the largest number of cows that can be satisfied. To demonstrate the issue, consider four cows with grazing ranges 3..5, 4..8, 1..2, and 5..10; below is a schematic of their grazing ranges: 1 2 3 4 5 6 7 8 9 10 11 12 13 |---|---|---|---|---|---|---|---|---|---|---|---|-... aaaaaaaaa bbbbbbbbbbbbbbbbb ccccc ddddddddddddddddddddd As can be seen, the first, second and fourth cows share the point 5, but the third cow's grazing range is disjoint. Thus, a maximum of 3 cows can have the soda machine within their grazing range. PROBLEM NAME: soda INPUT FORMAT: * Line 1: A single integer: N * Lines 2..N+1: Line i+1 contains two space-separated integers: A_i and B_i SAMPLE INPUT (file soda.in): 4 3 5 4 8 1 2 5 10 OUTPUT FORMAT: * Line 1: A single integer representing the largest number of cows whose grazing intervals can all contain the soda machine. SAMPLE OUTPUT (file soda.out): 3 OUTPUT DETAILS: If the soda machine is placed at location 5, cows 1, 2, and 4 can be satisfied. It is impossible to satisfy all four cows. **********************************************************************