加油问题
Time Limit: 1 Seconds Memory Limit: 32768 K
Total Submit:351 Accepted:84
--------------------------------------------------------------------------------
Description
输入的第一行是一个正整数k,表示测试例个数。接下来几行是k个测试例的数据,每个测试例的数据由三行组成,其中第一行含4个正实数,依次为A和B两个城市之间的距离d1、汽车油箱的容量c(以升为单位)、每升汽油能行驶的距离d2、沿途油站数n (1<=n<=200);第二行含n个实数d1, d2 ,…, dn,表示各油站离出发点的距离(d1=0);第三行含n个实数p1, p2 ,…, pn,表示各油站每升汽油的价格。同一行的数之间用一个空格隔开。
Input
输入的第一行是一个正整数k,表示测试例个数。接下来几行是k个测试例的数据,每个测试例的数据由三行组成,其中第一行含4个正整数,依次为A和B两个城市之间的距离d1、汽车油箱的容量c(以升为单位)、每升汽油能行驶的距离d2、沿途油站数n (1<=n<=200);第二行含n个实数d1, d2 ,…, dn,表示各油站离出发点的距离(d1=0);第三行含n个实数p1, p2 ,…, pn,表示各油站每升汽油的价格。同一行的数之间用一个空格隔开。
Output
对于每个测试例输出一行,含一个实数,表示从城市A到城市B所要花费的最少油费(输出的结果精确到小数点后一位)。若问题无解,则输出“No Solution”。
Sample Input
2
1500 50 10 4
0 300.0 800.0 1200.0
4.0 5.0 4.0 4.5
1000 40 10 3
0 500.0 750.0
4.5 5.0 4.2
Sample Output
640.0
No Solution
Source
算法设计作业