C++

Forum

 
Solving car fueling problem

marialavr (6)
I am trying to solve the car fueling problem. The problem sounds like this:

You are going to travel to another city that is located 𝑑 miles away from your home city. Your car can travel at most π‘š miles on a full tank and you start with a full tank. Along your way, there are gas stations at distances stop1, stop2, . . . , stop𝑛 from your home city. What is the minimum number of refills needed?

Problem Description
Input Format. The first line contains an integer 𝑑. The second line contains an integer π‘š. The third line
specifies an integer 𝑛. Finally, the last line contains integers stop1, stop2, . . . , stop𝑛.
Output Format. Assuming that the distance between the cities is 𝑑 miles, a car can travel at most π‘š miles
on a full tank, and there are gas stations at distances stop1, stop2, . . . , stop𝑛 along the way, output the
minimum number of refills needed. Assume that the car starts with a full tank. If it is not possible to
reach the destination, output βˆ’1.
Constraints. 1 ≀ 𝑑 ≀ 105. 1 ≀ π‘š ≀ 400. 1 ≀ 𝑛 ≀ 300. 0 < stop1 < stop2 < Β· Β· Β· < stop𝑛 < 𝑑.

My problem is that the second while loop goes up to currentRefill = 5, so the further conditions are not met. So I end up with wrong value.
To check the code I am provided with 3 examples:

First:
950
400
4
200 375 550 750

Second:
10
3
4
1 2 5 9

Third:
200
250
2
100
150


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
  #include <iostream>
#include <vector>

using namespace std; 

//Function that returns the total number of refills made to reach the destination of N km

int MinRefills( int n, int milesAway, vector<int> Stops, int fulltank) { 
    int numRefills = 0;
    int currentRefill = 0;
    int lastRefill = 0;
    
    if ((Stops[currentRefill] + fulltank) >= milesAway) {
        return numRefills;
    }

    while (currentRefill <= n) {
        lastRefill = currentRefill; 
        while ((currentRefill <= n) && ((Stops[currentRefill + 1] - Stops[lastRefill]) <= fulltank)) {
            currentRefill = currentRefill + 1;
            cout << currentRefill << Stops[currentRefill] << "\t"; //printing to check 
        }
        if (currentRefill == lastRefill) {
            //cout << "-1";
            return -2;
        }
        if (currentRefill <= n) {
            //cout << numRefills;
            numRefills = numRefills + 1;
        }
        if ((Stops[currentRefill] + fulltank) >= milesAway) {
            cout << "Not bullshit" << Stops[currentRefill + 1];
            return numRefills++;
        }
    }
    return numRefills; 
}

int main() {
    int milesAway, fulltank, n, stopValue; 
    vector<int> Stops;
    cin >> milesAway;
    cin >> fulltank; 
    cin >> n; 
    Stops.push_back(0);
    if (n == 4) {
        int stop1, stop2, stop3, stop4;
        cin >> stop1 >> stop2 >> stop3 >> stop4;
        Stops.push_back(stop1);
        Stops.push_back(stop2);
        Stops.push_back(stop3);
        Stops.push_back(stop4); 
    }
    else { 
       for ( int i = 0; i < n; i++) {
         cin >> stopValue; 
         Stops.push_back(stopValue);
         //cout << Stops.size();
       }
    }
    cout << MinRefills(n, milesAway, Stops, fulltank);
    return 0;
}
lastchance (6980)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
    while (currentRefill < n) {
        lastRefill = currentRefill; 
        while ( ( currentRefill < n ) && ( (Stops[currentRefill + 1] - Stops[lastRefill]) <= fulltank ) )
        {
            currentRefill = currentRefill + 1;
        }
        
        cout << currentRefill << "  " << Stops[currentRefill] << "\n"; //printing to check 
        
        if (currentRefill == lastRefill)
        {
            return -1;
        }
        numRefills = numRefills + 1;
        
        if ((Stops[currentRefill] + fulltank) >= milesAway)
        {
            return numRefills;
        }
    }
    return -1;
marialavr (6)
Thank you a lot. Could you help me with the explanation, please?
lastchance (6980)
marialavr wrote:
Could you help me with the explanation, please?


Well, it's basically your code! So you can compare the (minor) differences: you seem to have been on the right track. The main issues were with <= n or < n, for which the best way is probably to talk your way through your first example.

Note that the last index of Stops[] is n (for the way you have set it up, which is OK), so trying to do Stops[currentRefill + 1] would have gone beyond the end of the array.
Last edited on
marialavr (6)
Thank you. Yes, I was wondering how I could overcome this issue with the out of bounds.
Topic archived. No new replies allowed.