Order execution is a key component in financial investment, which is the step to adjust the portfolio in real. For example, in stock investment, the investor might want to adjust the position (held amount) of its held instrument (stock) at the beginning of the day, and he/she expects the adjustment is done by the end of the day. If the desired position goes down, he/she needs to sell some stocks; if it goes up, he/she needs to buy some. So he makes an "order" at the very beginning of the day, and expects the order to be "executed" in this day.
The timing in which he/she buys/sells the stock has an impact on the profit. For example, if the stock price goes down, selling it in the morning is better than afternoon. The problem that on which time slots the investor should do the liquidation/acquisition (buying/selling) to obtain the desired position is called order execution. In a typical setting of such problem, only past market information can be observed, and it can be reduced into a sequential decision making problem, but we are doing something different in this problem. Instead of trying to predict the "unpredictable" market, for the scope of this task, you can given the market information of the whole time horizon (one day in our case). The task is to find out the best timing to execute an intraday order, so that the profit is maximized.
We set this task on China A-shares market, which are the stock shares of mainland China-based companies that trade on the two Chinese stock exchanges, the Shanghai Stock Exchange (SSE) and the Shenzhen Stock Exchange (SZSE). In our setting, the finest-grained execution step duration is one minute. A-shares market has 240 minutes (9:30-11:30, 13:00-15:00) every day, which means you will have 240 chances. In each minute, you can decide to buy/sell some shares. The cash change is the deal price per share on that minute times the traded shares. Note that, if you have a "SELL" order, you cannot buy any share on that day; if the order is in "BUY" direction, you cannot sell any.
The shares you can buy/sell on a particular minute is limited by the market volume on that minute. This limitation should be carefully computed so that the impact on market price is taken into account even during the simulation. For simplicity, we give a "safe" volume for each minute, which is the maximum number of shares that is available for trade in that minute. Also, on A-shares market, the minimum trading unit is "one lot", which is 100 shares, meaning that the shares to trade on a particular minute must be a multiple of 100.
If on one minute, the trading algorithm gives a non-zero volume, i.e., it desires to buy/sell some shares (a multiple of 100 shares of course), the exchange will make the deal, and also charge for the deal. This includes the handling fee, government tax and etc. The charge is 0.03% of the trade value (which is the cash you pay/earn for the trading itself), rounded to cents (cents means 0.01 yuan). If the charge is less than 5 Chinese yuan, it will be 5 yuan.
输入描述:
The first line of input is one integer T (
), stating that there will be T test cases.
In each case, we show an order along with the market information on that day, which has 241 lines.
In the first line, there is a word BUY or SELL, followed by a space and a number a (
, a is a multiple of 100), which is the shares of the order to execute.
The following 240 lines are the market information from 9:30 to 15:00. Each line has two number, separated by space. The first is price
(
), rounded to cents, and the second is the maximum number of shares availble for trading on that minute
(
).
It is guaranteed that the orders can all be completely executed.
The sum of a from all test cases does not exceed
.
输出描述:
Output one number of each test case, which is the maximum cash balance (cash on account at the end of the day minus cash at the beginning), rounded to cents.
示例1
输入
复制
1
BUY 101600
3.07 4734400
3.04 1343900
3.04 637400
3.03 658100
3.03 471100
3.03 574000
3.04 646400
3.04 359100
3.02 1290200
3.02 231200
3.02 292800
3.01 276300
3.01 906600
3.02 614902
3.02 263900
3.02 298998
3.02 112000
3.03 466902
3.03 428000
3.03 209100
3.03 100500
3.02 534300
3.02 755800
3.01 194400
2.99 2646800
3.00 480100
3.01 267200
3.00 103900
3.01 211600
3.00 288200
3.01 306900
3.01 203600
3.00 190500
3.00 77900
3.00 171700
3.01 241800
3.01 161700
3.01 72300
3.00 166400
3.00 261300
3.01 322100
3.02 399800
3.02 134600
3.02 104700
3.02 165700
3.01 252300
3.01 248800
3.00 126200
3.01 323500
3.01 149800
3.01 67700
3.01 131400
3.01 237900
3.01 169900
3.02 112600
3.02 245800
3.02 108100
3.01 89200
3.02 51100
3.02 112500
3.01 36400
3.02 186700
3.02 106200
3.02 94600
3.02 58600
3.01 170800
3.01 69300
3.01 69200
3.02 38000
3.01 65100
3.02 139200
3.02 147900
3.02 56800
3.02 79500
3.01 52400
3.02 54100
3.02 102000
3.02 43700
3.01 174800
3.02 89800
3.01 150200
3.02 839200
3.02 20200
3.02 126600
3.01 15700
3.02 148800
3.02 185700
3.01 86200
3.01 51100
3.01 52600
3.02 73900
3.02 47600
3.01 814900
3.00 107000
3.00 108000
3.00 200300
3.01 138300
3.00 1272300
3.00 82200
3.00 153000
2.99 165900
2.99 103500
3.00 836500
2.99 157700
3.00 407900
2.99 249700
2.98 1284300
2.98 312000
2.98 110200
2.97 1881453
2.98 738200
2.97 913500
2.97 723100
2.97 732653
2.97 237800
2.96 328800
2.96 1358047
2.95 531700
2.96 766200
2.97 186553
2.99 1096800
2.99 819547
2.98 198400
2.98 195700
2.99 850400
2.98 424700
2.99 184700
3.00 309700
2.99 322600
2.99 95000
2.99 52700
2.99 39100
3.00 88400
2.99 147600
2.99 121300
2.99 114500
2.98 133200
2.98 284300
2.98 220200
2.98 78700
2.98 33300
2.99 12700
2.98 79300
2.99 115700
2.99 135100
2.98 117000
2.99 27800
2.98 18200
2.99 99400
2.98 43000
2.98 76000
2.98 120000
2.99 55400
2.98 411400
2.99 201100
2.98 24600
2.98 52400
2.98 38700
2.99 149500
2.98 134000
3.00 646900
3.00 44300
2.99 104000
2.99 95300
2.99 75800
2.99 59400
2.99 83700
2.99 76700
2.99 50200
3.00 91500
2.99 308500
2.99 235600
2.99 77100
2.99 38900
2.99 43100
2.99 433600
2.99 53100
2.98 332200
2.99 69900
2.99 37000
2.98 75400
2.98 41200
2.98 5400
2.98 41000
2.99 37800
2.98 51200
2.98 31100
2.99 33000
2.99 114100
2.99 127300
2.98 502600
2.98 268300
2.99 24700
2.98 64100
2.98 74700
2.98 221400
2.98 90600
2.97 149800
2.98 254000
2.98 71700
2.98 77800
2.99 280200
2.98 30500
2.97 171400
2.97 193900
2.97 109300
2.98 337700
2.97 171400
2.98 193300
2.97 88800
2.98 42900
2.97 267300
2.98 104700
2.98 39200
2.98 71700
2.98 348500
2.98 104100
2.98 211000
2.98 231800
2.98 64600
2.99 63000
2.98 109100
2.99 54000
2.98 63800
2.98 124100
2.98 481300
2.99 125300
2.98 196100
2.98 382300
2.98 92900
2.98 162000
2.98 291400
2.99 318000
2.99 339200
2.98 602700
2.98 719100
2.99 395000
2.99 516033
2.99 516033
2.99 516033