Fuel Station Route Optimization

Problem Analysis

The challenge involves navigating from Hangzhou to a destination with an initially empty fuel tank. Given information about multiple gas stations, we need to determine if the destination is reachable and calculate the minimum cost if possible. If unreachable, we must find the maximum distance that can be traveled.

The input includes: tank capacity (Cmax), total distance (D), fuel efficiency (Davg), and number of stations (N). Subsequent lines provide each station's price and distance from the starting point.

Key Considerations

1. Account for existing fuel in the tank when refueling
2. When all reachable stations have higher prices than the current station, don't jump to the immediate next station
3. Instead, identify the station with the lowest relative price among reachable options

Algorithm Strategy

1. Assume starting position at 0 km (Hangzhou)
2. Sort stations by distance, adding the destination as a station with zero price
3. If no station exists at starting position, travel distance is 0
4. For each current station:
   • If a cheaper station is reachable, add just enough fuel to reach it
   • If no cheaper station exists, find the least expensive reachable station and fill the tank completely
   • If no station is reachable, calculate maximum possible travel distance and terminate

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct GasStop {
    double price;
    double distance;
};

bool distanceSort(GasStop a, GasStop b) {
    return a.distance < b.distance;
}

int main() {
    double tankCapacity, totalDistance, fuelPerUnit;
    int stationCount;
    
    while (cin >> tankCapacity >> totalDistance >> fuelPerUnit >> stationCount) {
        vector<GasStop> stops(stationCount);
        
        for (int i = 0; i < stationCount; i++) {
            cin >> stops[i].price >> stops[i].distance;
        }
        
        stops.push_back({0.0, totalDistance});
        sort(stops.begin(), stops.end(), distanceSort);
        
        if (stops[0].distance > 0.001) {
            printf("The maximum travel distance = 0.00\n");
            continue;
        }
        
        int currentPos = 0;
        double currentFuel = 0.0;
        double totalCost = 0.0;
        double maxRange = tankCapacity * fuelPerUnit;
        bool canReach = true;
        
        while (currentPos < stationCount) {
            int nextStop = -1;
            double minPrice = 1e9;
            
            for (int i = currentPos + 1; i <= stationCount && stops[i].distance <= stops[currentPos].distance + maxRange; i++) {
                if (stops[i].price < minPrice) {
                    minPrice = stops[i].price;
                    nextStop = i;
                    if (minPrice < stops[currentPos].price) break;
                }
            }
            
            if (nextStop == -1) {
                canReach = false;
                break;
            }
            
            double needed = (stops[nextStop].distance - stops[currentPos].distance) / fuelPerUnit;
            
            if (stops[nextStop].price < stops[currentPos].price) {
                if (needed > currentFuel) {
                    totalCost += (needed - currentFuel) * stops[currentPos].price;
                    currentFuel = 0;
                } else {
                    currentFuel -= needed;
                }
            } else {
                totalCost += (tankCapacity - currentFuel) * stops[currentPos].price;
                currentFuel = tankCapacity - needed;
            }
            
            currentPos = nextStop;
        }
        
        if (!canReach) {
            printf("The maximum travel distance = %.2f\n", stops[currentPos].distance + maxRange);
        } else {
            printf("%.2f\n", totalCost);
        }
    }
    
    return 0;
}

Toxic Liquid Concentration Mixing

Problem Analysis

This problem involves mixing liquids with different concentrations. A common error is assuming equal volumes when mixing, leading to incorrect concentration calculations. The actual concentration must account for the varying volumes of the mixed liquids.

Critical Insight

When mixing liquids, the concentration calculation should be: new_concentration = (current_concentration × current_volume + new_liquid_concentration × new_volume) / (current_volume + new_volume)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int testCases;
    cin >> testCases;
    
    while (testCases--) {
        int bottleCount, bottleVolume, maxConcentration;
        cin >> bottleCount >> bottleVolume >> maxConcentration;
        
        vector<int> concentrations(bottleCount);
        for (int i = 0; i < bottleCount; i++) {
            cin >> concentrations[i];
        }
        
        sort(concentrations.begin(), concentrations.end());
        
        if (concentrations[0] > maxConcentration) {
            cout << "0 0.00" << endl;
            continue;
        }
        
        double currentConc = concentrations[0];
        int totalVolume = bottleVolume;
        
        for (int i = 1; i < bottleCount; i++) {
            double newConc = (currentConc * totalVolume + concentrations[i] * bottleVolume) / (totalVolume + bottleVolume);
            
            if (newConc > maxConcentration) break;
            
            currentConc = newConc;
            totalVolume += bottleVolume;
        }
        
        printf("%d %.2f\n", totalVolume, currentConc / 100);
    }
    
    return 0;
}