NOI '07 P2 - Cash Exchange

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem type
National Olympiad in Informatics, China, 2007

Little Y has recently been working at a currency exchange center. The currency exchange center only offers two types of vouchers to be exchanged: commemorative voucher A (henceforth known as voucher A) and commemorative voucher B (henceforth known as voucher B). All voucher-holding customers possess their very own account. The quantity of vouchers a customer has may be a real number.

Rising and falling daily with the waves of the market, the two types of vouchers each has their own values at any given time, and each unit of a voucher can be traded that day for some amount of cash. We note that on day K, the values of voucher A and voucher B are respectively A_K and B_K (dollars/unit voucher).

To make it more convenient for customers, the exchange center offers a very easy system to make transactions: the ratio exchange method. There are two different aspects to the ratio exchange method:

  1. Selling vouchers: the customer provides a real number OP in the range [0, 100] as the selling ratio. This means that OP\% of voucher A and OP\% of voucher B are exchanged for cash with the rate at that point in time.
  2. Buying vouchers: the customer pays IP dollars, and the exchange center takes this money to exchange it for vouchers. Furthermore, the ratio between the value of voucher A and voucher B on day K just happens to be Rate_K.

For example, let's assume for the next 3 three days the following changes in the values of A_K, B_K, and Rate_K:

Time A_K B_K Rate_K
Day 1 1 1 1
Day 2 1 2 2
Day 3 2 2 3

Let's say that on one day, a customer has 100 dollars but no vouchers of any kind. The customer carries out the following transactions:

Time Transaction Cash (Dollars) Voucher A Voucher B
Initial None 100 0 0
Day 1 Buy — 100 dollars 0 50 50
Day 2 Sell — 50\% 75 25 25
Day 2 Buy — 60 dollars 15 55 40
Day 3 Sell — 100\% 205 0 0

Note that there may be multiple transactions on a single day.

Little Y is a very economically-minded worker. After a relatively long time conducting operations and market estimates, he already knows within the future N days what the values of vouchers A and B, as well as the rate, will be. He wishes to calculate, if one starts with S dollars, what is the maximum amount of cash (in dollars) that can be obtained after N days.

Input Specification

The first line contains two positive integers N and S, representing the number of days that little Y's can foresee and the starting amount of cash respectively.
Within the next N lines, the K-th line contains three real numbers A_K, B_K, and Rate_K.

Output Specification

Output a single real number MaxProfit, indicating the maximum amount of cash in dollars that can be obtained after all operations on the N-th day has finished, accurate to 3 decimal places. Your answer will be considered correct if its absolute difference with the correct answer is no larger than 0.001.

Sample Input

3 100
1 1 1
1 2 2
2 2 3

Sample Output



Time Transaction Cash (Dollars) Voucher A Voucher B
Initial None 100 0 0
Day 1 Buy — 100 dollars 0 50 50
Day 2 Sell — 100\% 150 0 0
Day 2 Buy — 150 dollars 0 75 37.5
Day 3 Sell — 100\% 225 0 0


The test data ensures that the precision needed for calculations will not exceed 10^{-7}.
For 40\% of the test cases, N \le 10;
For 60\% of the test cases, N \le 1\,000;
For 100\% of the test cases, N \le 100\,000;
For 100\% of the test cases:

  • 0 < A_K \le 10;
  • 0 < B_K \le 10;
  • 0 < Rate_K \le 100;
  • MaxProfit \le 10^9.


The input may be very large, please use faster methods of input.
There must be an optimal series of transaction satisfying the conditions:

  • each buying transaction uses up all of the cash, and
  • each selling transaction sells all of the vouchers.

Problem translated to English by Alex.


There are no comments at the moment.