I am spinning with this problem for half day of thoughts and bugs. I would like to share it here with you so that we can discuss together to find some interesting things (more than a solution!).
You are the player having T dollars, and you will trade on n types of commodities. The game takes place in R turns. Each turn, the price of each type is announced, and you are allowed to buy or sell goods:
If you want to buy s[i] products of type-i, you have to pay money. Your bank account will be decreased by s[i] * (P[i] + d), where P[i] is the price of type-i, d is the extra fee in buying. s[i] products that you just bought would be transported to the storage. You cannot have more than C[i] products of type-i in your storage.
If you want to sell s[i] products of type-i, of courses you must have at least s[i] products of type-i in the storage, which will be decreased by s[i]. After that, your bank account is gained by s[i] * (P[i] — e), where e is the extra fee in selling.
What is the biggest money in your bank account after all?
Notice: In each turn, the order of buying/selling any types is not important. But make sure that at the end of that turn, your money cannot be negative.
- The first line contains 5 non-negative integers n, T, R, d, e.
- The second line contains n non-negative integers C, C, ..., C[n]
- The next R lines, every line consists of n non-negative integers, which are P, P, ..., P[n] in the turn.
3 2 2 1 0
1 1 1
1 1 1
2 3 4
T <= 10^9
d,e <= 10^6
C[i] <= 20
n <= 5
R <= 500
Note: When R > 5, d = e = 0.
This is my code
(Simple recursive + Greedy)
I will sell when the price is highest, and try to buy when the price is lowest. I am thinking about dynamic programming way, but it seems hard to me.
I cannot figure out any more efficient solution. Any suggestion, ideas, reference sources would be appreciated.