a658: NOI2012 Day1.2.骑行川藏
Tags :
Accepted rate : 7人/9人 ( 78% ) [非即時]
評分方式:
Tolerant

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

Content

 蛋蛋非常热衷于挑战自我,今年暑假他准备沿川藏线骑着自行车从成都前往拉萨。川藏线的沿途有着非常美丽的风景,但在这一路上也有着很多的艰难险阻,路况变化多端,而蛋蛋的体力十分有限,因此在每天的骑行前设定好目的地、同时合理分配好自己的体力是一件非常重要的事情。

 由于蛋蛋装备了一辆非常好的自行车,因此在骑行过程中可以认为他仅在克服风阻做功(不受自行车本身摩擦力以及自行车与地面的摩擦力影响)。某一天他打算骑N段路,每一段内的路况可视为相同:对于第i段路,我们给出有关这段路况的3个参数 ,其中si表示这段路的长度,ki表示这段路的风阻系数,vi'表示这段路上的风速(vi'>0 表示在这段路上他遇到了顺风,反之则意味着他将受逆风影响)。若某一时刻在这段路上骑车速度为v,则他受到的风阻大小为F=ki(vi-vi')2 (这样若在长度为si 的路程内保持骑行速度vi不变,则他消耗能量(做功)E=ki(vi-vi’)2si)。

设蛋蛋在这天开始时的体能值是EU,请帮助他设计一种行车方案,使他在有限的体力内用最短的时间到达目的地。请告诉他最短的时间T是多少。

Input

输入中的第一行包含一个正整数N和一个实数EU,分别表示路段的数量以及蛋蛋的体能值。

接下来N行分别描述N个路段,每行有3个实数si,ki,vi,分别表示第i段路的长度,风阻系数以及风速。
Output

输出一个实数T,表示蛋蛋到达目的地消耗的最短时间,要求至少保留到小数点后6。這裡規定與原題不同,請四捨五入到小數點後8位。

Sample Input
3 10000
10000 10 5
20000 15 8
50000 5 6
Sample Output
12531.34496464
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1K
公開 測資點#9 (5%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
Hint :

 【样例说明】

 一种可能的方案是:蛋蛋在三段路上都采用匀速骑行的方式,其速度依次为5.12939919, 8.03515481,6.17837967

【数据规模与约定】

对于10% 的数据,N=1

对于40% 的数据,N≤2

对于60% 的数据,N≤100

对于80% 的数据,N≤1000

对于所有数据,N≤100000≤EU≤1080<si≤1000000<ki≤15100<vi<100。数据保证最终的答案不会超过105

 【提示】

必然存在一种最优的体力方案满足:蛋蛋在每段路上都采用匀速骑行的方式。 

Tags:
出處:
NOI2012Day1第二题 [管理者:
david942j (文旋)
]


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