P4027 [NOI2007] Currency Exchange

Xiao Y (pinyin) recently started working at a voucher exchange. This exchange issues and trades only two types of vouchers: A commemorative voucher (hereinafter A voucher) and B commemorative voucher (hereinafter B voucher). Each customer who holds vouchers has their own account. The quantities of vouchers can be real numbers. With daily market fluctuations, the two vouchers each have their current value, i.e., each unit of voucher can be exchanged for a certain amount of RMB on that day. We record the values of A and B vouchers on day $K$ as $A_K$ and $B_K$ (yuan per unit voucher), respectively. For customer convenience, the exchange provides a very convenient trading method: proportional trading. Proportional trading has two aspects: a) Sell vouchers: The customer provides a real number $OP$ in $[0, 100]$ as the selling ratio, meaning: exchange $OP\%$ of A vouchers and $OP\%$ of B vouchers into RMB at the current values. b) Buy vouchers: The customer pays $IP$ RMB, and the exchange will convert it into vouchers with a total value of $IP$, and the proportion of A and B vouchers provided to the customer will be exactly $\mathrm{Rate}_ K$ on day $K$. For example, suppose over the next $3$ days the changes of $A_K$, $B_K$, and $\mathrm{Rate}_ K$ are as follows: | Time | $A_K$ | $B_K$ | $\mathrm{Rate}_ K$ | | ----- | ----- | ----- | ----- | | Day 1 | $1$ | $1$ | $1$ | | Day 2 | $1$ | $2$ | $2$ | | Day 3 | $2$ | $2$ | $3$ | Assume that on day 1, the user has $100$ RMB yuan and no vouchers. The user can perform the following operations: | Time | User operation | RMB (yuan) | Quantity of A vouchers | Quantity of B vouchers | | ----- | ----- | ----- | ----- | ----- | | Account opening | None | $100$ | $0$ | $0$ | | Day 1 | Buy $100$ yuan | $0$ | $50$ | $50$ | | Day 2 | Sell $50\%$ | $75$ | $25$ | $25$ | | Day 2 | Buy $60$ yuan | $15$ | $55$ | $40$ | | Day 3 | Sell $100\%$ | $205$ | $0$ | $0$ | Note that multiple operations can be performed on the same day. Xiao Y is financially savvy. Through long-term operations and market estimation, he already knows the values of A and B vouchers and $\mathrm{Rate}$ for the next $N$ days. He also wants to compute, if he starts with $S$ RMB yuan, what is the maximum amount of money he can obtain after $N$ days.

The first line contains two positive integers $N, S$, representing the number of days Xiao Y can foresee and the initial amount of money, respectively. The next $N$ lines each contain three real numbers $A_K, B_K, \mathrm{Rate} _ K$ on line $K$, as described above.

Output a single real number $\mathrm{MaxProfit}$, the maximum amount of money obtainable by the end of day $N$. The answer should be rounded to $3$ decimal places.

| Time | User operation | RMB (yuan) | Quantity of A vouchers | Quantity of B vouchers | | ----- | ----- | ----- | ----- | ----- | | Account opening | None | $100$ | $0$ | $0$ | | Day 1 | Buy $100$ yuan | $0$ | $50$ | $50$ | | Day 2 | Sell $100\%$ | $150$ | $0$ | $0$ | | Day 2 | Buy $150$ yuan | $0$ | $75$ | $37.5$ | | Day 3 | Sell $100\%$ | $225$ | $0$ | $0$ | There is no partial credit for this problem. Your program’s output must not differ from the standard answer by more than $0.001$ to receive full credit for a test point; otherwise, you get no points. The testdata is designed such that the precision error will not exceed $10^{-7}$. For $40\%$ of the testdata, $N \le 10$. For $60\%$ of the testdata, $N \le 1\,000$. For $100\%$ of the testdata, $N \le 10^5$. For $100\%$ of the testdata, the following hold: $0 < A_K \leq 10$, $0 < B_K \le 10$, $0 < \mathrm{Rate}_K \le 100$, $\mathrm{MaxProfit} \leq 10^9$. The input file may be large; please use fast I/O. There always exists an optimal buy/sell strategy that satisfies: each buy operation uses up all RMB, and each sell operation sells all vouchers. Translated by ChatGPT 5