a199: NOI2007 Day1.2.货币兑换
Tags :
Accepted rate : 8人/11人 ( 73% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 03:18

Content

小Y 最近在一家金券交易所工作。该金券交易所只发行交易两种金券:A 纪
念券(以下简称A 券)和B 纪念券(以下简称B 券)。每个持有金券的顾客都有
一个自己的帐户。金券的数目可以是一个实数。


每天随着市场的起伏波动,两种金券都有自己当时的价值,即每一单位金券
当天可以兑换的人民币数目。我们记录第K 天中A 券和B 券的价值分别为AK和
BK(元/单位金券)。


为了方便顾客,金券交易所提供了一种非常方便的交易方式:比例交易法。
比例交易法分为两个方面:


a) 卖出金券:顾客提供一个[0,100]内的实数OP 作为卖出比例,其意
义为:将OP%的A 券和OP%的B 券以当时的价值兑换为人民币;
b) 买入金券:顾客支付IP 元人民币,交易所将会兑换给用户总价值为
IP 的金券,并且,满足提供给顾客的A 券和B 券的比例在第K 天恰好为RateK;

例如,假定接下来3 天内的Ak、Bk、RateK 的变化分别为:

时间

AkBkRatek
第一天111
第二天122
第三天223

假定在第一天时,用户手中有100 元人民币但是没有任何金券。
用户可以执行以下的操作:

时间用户操作人民币()A 券的数量B 券的数量
开户10000
第一天买入100 05050
第二天卖出50%752525
第二天买入60 155540
第三天卖出100%20500

注意到,同一天内可以进行多次操作。


小Y 是一个很有经济头脑的员工,通过较长时间的运作和行情测算,他已经
知道了未来N 天内的A 券和B 券的价值以及Rate。他还希望能够计算出来,如
果开始时拥有S 元钱,那么N 天后最多能够获得多少元钱。

Input

第一行两个正整数N、S,分别表示小Y 能预知的天数以及初始时拥有的钱数。

接下来 N 行,第K 行三个实数AK、BK、RateK,意义如题目中所述。

Output
只有一个实数MaxProfit,表示第N 天的操作结束时能够获得的最大的金钱
数目。答案保留3 位小数。
Sample Input
3 100
1 1 1
1 2 2
2 2 3
Sample Output
225.000
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 2.0s , <1K
公開 測資點#1 (10%): 2.0s , <1K
公開 測資點#2 (10%): 2.0s , <1K
公開 測資點#3 (10%): 2.0s , <1K
公開 測資點#4 (10%): 2.0s , <1M
公開 測資點#5 (10%): 2.0s , <1M
公開 測資點#6 (10%): 2.0s , <10M
公開 測資點#7 (10%): 2.0s , <10M
公開 測資點#8 (10%): 2.0s , <10M
公開 測資點#9 (10%): 2.0s , <10M
Hint :

【样例说明】

时间用户操作人民币()A 券的数量B 券的数量
开户10000
第一天买入100 05050
第二天卖出100%15000
第二天买入150 07537.5
第三天卖出100%22500

【数据规模和约定】

测试数据设计使得精度误差不会超过10-7
对于40%的测试数据,满足N ≤ 10;
对于60%的测试数据,满足N ≤ 1 000;
对于100%的测试数据,满足N ≤ 100 000;
对于 100%的测试数据,满足:
0 < AK ≤ 10;
0 < BK ≤ 10;
0 < RateK ≤ 100
MaxProfit ≤ 109

【提示】

输入文件可能很大,请采用快速的读入方式。
必然存在一种最优的买卖方案满足:
·每次买进操作使用完所有的人民币;
·每次卖出操作卖出所有的金券。

Tags:
出處:
NOI2007Day1第二题 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」