/ OIer TK / 题库 /

骑行川藏

骑行川藏

测试数据来自 system/1805

描述

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

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

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

格式

输入格式

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

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

输出格式

输出一个实数 T,表示蛋蛋到达目的地消耗的最短时间,__要求恰好保留8位小数。你的输出必须和标准输出完全一样才能得分。__
(没办法……没有Special Judge)

样例1

样例输入1

3 10000
10000 10 5
20000 15 8
50000 5 6

样例输出1

12531.34496464

限制

对于10%的数据,N=1;
对于40%的数据,N≤2;
对于60%的数据,N≤100;
对于80%的数据,N≤1000;
对于所有数据,N≤10000,0≤Eu≤10^8,0<si≤100000,0<ki≤1,-100<vi'<100。数据保证最终的答案不会超过10^5。

单个测试点的时间限制为1s

提示

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

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

来源

NOI2012 Day 1 P2

信息

ID
1746
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者