Sane's Monthly Algorithms Challenge: November 2008
Stock Market II (Junior Level)
You have illegally obtained some insider information about the
projected trend of a particular stock over the next 24 hours. With this
information, you plan to repeatedly buy and sell the stock according to
what will rake in the most profit.
The information consists of
nvalues, each being the value of the stock at each time interval over a period of 24 hours. To buy one share of the stock, you must pay the value predicted for the current interval. To sell one share of the stock, you will receive the value predicted for that interval.
In the first Stock Market Challenge (July's SMAC Challenge), you were attempting to avoid rousing suspicion with your 1000 shares by only making one transaction. But this time you will be greedy: You may buy and sell the 1000 shares an unlimited number of times throughout the day (as long as you do not have more than 1000 in your holding at any one moment).
However, you will also need to pay a fixed commission rate to your broker on each transaction (every buy and every sell).
Using the stock’s projection, determine the optimum times to buy then sell, and the resulting maximum profit. It is always guaranteed that a profit can be made.
InputOn the first line is the integer
n≤ 1,000,000), and the fixed integer amount of commission per transaction.
On the next
nlines are the prices for the ith time intervals (1 ≤
i≤ n). Each line contains a floating point number with no more than 2 decimal places, representing the share’s price for the ith time interval.
OutputOutput the maximum possible integer profit made in dollars, respectively.
Grading:For 10 of the 15 test files, there will be no commission.
Sample Input24 30
Explanation of Sample Data
1) Buy 1000 at 1.00 for - 1000 - 30 = - $1030 4) Sell 1000 at 1.07 for + 1070 - 30 = + $1040 6) Buy 1000 at 0.98 for - 980 - 30 = - $1010 10) Sell 1000 at 1.14 for + 1140 - 30 = + $1110 ------- $110
Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Jan 15, 2009
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3