UVA 11935 - Through the Desert

/*

Problem link

Type: Binary search

Algorithm:

class Event to store the information of an event.

class Journey to store the information of a journey (with fuel tank and events).

the ok() function:

  - For each event in the journey, we calculate the remaining fuel and update

    the value according to the type of the event.

  - If the remaining fuel is negative, the fuel tank is not enough.

  - If we can reach the end of the journey, the fuel tank is good enough.

the binarySearch() function:

  - We will look for the least value of the fuel tank that satisfies the ok() function.

*/

#include <iostream>

#include <cmath>

#include <cstdio>

#include <vector>

#include <string>

#include <cstring>

using namespace std;

const char* fi = "input.txt";

const int maxn = 100;

const double eps = 10E-9;

class Event {

public:

int x, y;

string type;

Event(int x, int y, string type) {

this->x = x;

this->y = y;

this->type = type;

}

Event() {

this->x = 0;

this->y = 0;

this->type = "";

}

};

class Journey {

public:

double gasLeft;

Event* events;

Journey(double gasLeft, Event events[]) {

this->gasLeft = gasLeft;

this->events = events;

}

};

Event a[maxn];

int n, maxDist;

bool readFile();

bool ok(Journey journey);

double binarySearch(double l, double r);

int main() {

while (readFile()) {

printf("%0.3f\n", binarySearch(0.01, maxDist*30));

}

return 0;

}

double binarySearch(double l, double r) {

double left, right, mid;

left = l, right = r;

while (right - left > eps) {

mid = (left+right)/2;

if (ok(Journey(mid, a))) {

right = mid;

} else left = mid;

}

if (ok(Journey(left, a))) return left;

else return right;

}

bool readFile() {

n = 0;

maxDist = 0;

while (true) {

int x, y;

string type;

cin >> x;

cin >> type;

maxDist = x > maxDist? x : maxDist;

if (type == "Fuel") {

cin >> type;

cin >> y;

type = "Fuel";

if (x == 0 && y == 0) return false;

a[n++] = Event(x, y, type);

} else {

if (type == "Leak" || type == "Mechanic") a[n++] = Event(x, 0, type);

else if (type == "Goal") {

a[n++] = Event(x, 0, type);

break;

} else if (type == "Gas") {

cin >> type;

type = "Gas";

a[n++] = Event(x, 0, type);

}

}

}

return true;

}

bool ok(Journey journey) {

int fuelRate = 0;

int leakRate = 0;

int previousX = 0, currentX = 0;

double fullGas = journey.gasLeft;

for (int i = 0; i < n; i++) {

currentX = journey.events[i].x;

journey.gasLeft -= (double)(currentX - previousX)*((double)fuelRate/100 + (double)leakRate);

if (journey.gasLeft < 0) return false;

if (journey.events[i].type == "Fuel") fuelRate = journey.events[i].y;

else if (journey.events[i].type == "Leak") leakRate++;

else if (journey.events[i].type == "Mechanic") leakRate = 0;

else if (journey.events[i].type == "Gas") journey.gasLeft = fullGas;

else break;

previousX = currentX;

}

return true;

}