fork download
copy 
  1. #include <iostream>
  2. using namespace std; 
  3.  
  4. // The function returns starting point if there is a possible solution, otherwise returns -1 
  5. int findStartingGasStation(int g[], int c[],int n) 
  6. { 
  7. 	// Considering first gas station as a starting point 
  8. 	int start = 0; 
  9. 	int end = 1; 
  10.  
  11. 	int curr_fuel = g[start] - c[start]; 
  12.  
  13. 	/* Now we run a loop while all gas stations are not visited And we have reached start gas station again with 0 or more petrol */
  14. 	while (end != start || curr_fuel < 0) 
  15. 	{ 
  16. 		// If current amount of gas in car becomes less than 0, then we remove the starting gas station from tour 
  17. 		while (curr_fuel < 0 && start != end) 
  18. 		{ 
  19. 			// Removing starting gas station's gas and adding it's cost.  
  20. 			curr_fuel -= g[start] - c[start]; 
  21. 			start = (start + 1) % n;   // Changing start
  22.  
  23. 			// If 0 is being considered as start again, then there is no possible solution 
  24. 			if (start == 0) 
  25. 			return -1; 
  26. 		} 
  27.  
  28. 		// Adding a gas station to current tour 
  29. 		curr_fuel += g[end] - c[end]; 
  30.  
  31. 		end = (end + 1) % n; // updating the end station
  32. 	} 
  33.  
  34. 	// Returning starting point 
  35. 	return start; 
  36. } 
  37.  
  38. int main(){
  39.     int g[]={6,3,7};
  40.     int c[]={4,6,3};  
  41.     int n = sizeof(g)/sizeof(g[0]);
  42.     cout << "Fuel and Cost for each gas station:" << endl;
  43.         for (int i = 0; i < n; ++i)
  44.         {
  45.             cout << "Station " << i << ": Fuel = " << g[i] << ", Cost = " << c[i] << endl;
  46.         }
  47.  
  48. 	int start = findStartingGasStation(g, c, n); 
  49.  
  50. 	(start == -1)? cout<<"No solution": cout<<"Starting Gas Station = "<<start; 
  51.  
  52. 	return 0; 
  53. }
Success #stdin #stdout 0.01s 5264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Fuel and Cost for each gas station:
Station 0: Fuel = 6, Cost = 4
Station 1: Fuel = 3, Cost = 6
Station 2: Fuel = 7, Cost = 3
Starting Gas Station = 2
https://ideone.com/DcymK7
language:
C++ 4.3.2 (gcc-4.3.2)
created:
35 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!