[UVA][二分答案] 11935 - Through the Desert
Through the Desert
| Through the Desert |
Imagine you are an explorer trying to cross a desert. Many dangers and obstacles are waiting on your path. Your life depends on your trusty old jeep having a large enough fuel tank. But how large exactly does it have to be? Compute the smallest volume needed to reach your goal on the other side.
The following events describe your journey:
Fuel consumption n
means that your truck needs n litres of gasoline per 100 km. n is an integer in the range [1..30]. Fuel consumption may change during your journey, for example when you are driving up or down a mountain.
Leak
means that your truck's fuel tank was punctured by a sharp object. The tank will start leaking gasoline at a rate of 1 litre of fuel per kilometre. Multiple leaks add up and cause the truck to lose fuel at a faster rate.
However, not all events are troublesome in this desert. The following events increase your chances of survival:
Gas station
lets you fill up your tank.
Mechanic
fixes all the leaks in your tank.
And finally:
Goal
means that you have safely reached the end of your journey!
Input
The input consists of a series of test cases. Each test case consists of at most 50 events. Each event is described by an integer, the distance (in kilometres measured from the start) where the event happens, followed by the type of event as above.
In each test case, the first event is of the form `0 Fuel consumption n', and the last event is of the form `d Goal' (d is the distance to the goal).
Events are given in sorted order by non-decreasing distance from the start, and the `Goal' event is always the last one. There may be multiple events at the same distance--process them in the order given.
Input is terminated by a line containing `0 Fuel consumption 0' which should not be processed.
Output
For each test case, print a line containing the smallest possible tank volume (in litres, with three digits precision after the decimal point) that will guarantee a successful journey.
Sample Input
0 Fuel consumption 10 100 Goal 0 Fuel consumption 5 100 Fuel consumption 30 200 Goal 0 Fuel consumption 20 10 Leak 25 Leak 25 Fuel consumption 30 50 Gas station 70 Mechanic 100 Leak 120 Goal 0 Fuel consumption 0
Sample Output
10.000 35.000 81.000
中文翻譯：http://rubyacm.blogspot.tw/2011/09/11935-through-desert.html
不過覺得應該要翻成找最小油箱的體積。
然後二分油箱體積去模擬整個過程，如果可以抵達終點就縮小。
一開始油箱一定是裝滿的。
#include <stdio.h>
#include <string.h>
#include <math.h>
struct E {
int d, n;
int cmd;
};
E D[1005];
int check(double volumn, int n) {
int i;
double v = volumn, prev = 0, cost = 0;
int leak = 0;
for(i = 0; i < n; i++) {
v -= (D[i].d-prev)*leak+(D[i].d-prev)/100.0*cost;
if(v < 0) return 0;
switch(D[i].cmd) {
case 0:cost = D[i].n; break;
case 1:leak++; break;
case 2:v = volumn; break;
case 3:leak = 0; break;
}
prev = D[i].d;
}
return 1;
}
int main() {
char s[50];
int d, n, m;
while(scanf("%d", &d) == 1) {
scanf("%*s %*s %d", &n);
if(n == 0) break;
m = 0;
D[m].d = d, D[m].n = n, D[m].cmd = 0;
m++;
while(scanf("%d %s", &d, s) == 2) {
if(s[0] == 'F') {
scanf("%*s %d", &n);
D[m].d = d, D[m].n = n, D[m++].cmd = 0;
}
else if(s[0] == 'L')
D[m].d = d, D[m++].cmd = 1;
else if(s[0] == 'G' && s[1] == 'a') {
scanf("%*s");
D[m].d = d, D[m++].cmd = 2;
} else if(s[0] == 'M')
D[m].d = d, D[m++].cmd = 3;
else {
D[m].d = d, D[m++].cmd = 4;
break;
}
}
double l = 0, r = 10000, f;
while(fabs(l-r) > 1e-8) {
f = (l+r)/2;
if(check(f, m))
r = f;
else
l = f;
}
printf("%.3lf\n", f);
}
return 0;
}