// C++ program to find circular tour for a truck
#include <bits/stdc++.h>
using namespace std;
// A petrol pump has petrol and distance to next petrol pump
class petrolPump {
public:
int petrol;
int distance;
};
// The function returns starting point if there is a
// possible solution, otherwise returns -1
int printTour(petrolPump p[], int n)
{
// deficit is used to store the value of the capacity as
// soon as the value of capacity becomes negative so as
// not to traverse the array twice in order to get the
// solution
int start = 0, deficit = 0;
int capacity = 0;
for (int i = 0; i < n; i++) {
capacity += p[i].petrol - p[i].distance;
if (capacity < 0) {
// If this particular step is not done then the
// between steps would be redundant
start = i + 1;
deficit += capacity;
capacity = 0;
}
}
return (capacity + deficit >= 0) ? start : -1;
}
// Driver code
int main()
{
petrolPump arr[] = {{3, }, { 6, 4 }, { 3, 6 }, { 7, 3 } };
int n = sizeof(arr) / sizeof(arr[0]);
int start = printTour(arr, n);
(start == -1) ? cout << "No solution"
: cout << "Start = " << start;
return 0;
}
// This code is contributed by aditya kumar
Ly8gQysrIHByb2dyYW0gdG8gZmluZCBjaXJjdWxhciB0b3VyIGZvciBhIHRydWNrCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gQSBwZXRyb2wgcHVtcCBoYXMgcGV0cm9sIGFuZCBkaXN0YW5jZSB0byBuZXh0IHBldHJvbCBwdW1wCmNsYXNzIHBldHJvbFB1bXAgewpwdWJsaWM6CglpbnQgcGV0cm9sOwoJaW50IGRpc3RhbmNlOwp9OwoKLy8gVGhlIGZ1bmN0aW9uIHJldHVybnMgc3RhcnRpbmcgcG9pbnQgaWYgdGhlcmUgaXMgYQovLyBwb3NzaWJsZSBzb2x1dGlvbiwgb3RoZXJ3aXNlIHJldHVybnMgLTEKaW50IHByaW50VG91cihwZXRyb2xQdW1wIHBbXSwgaW50IG4pCnsKCS8vIGRlZmljaXQgaXMgdXNlZCB0byBzdG9yZSB0aGUgdmFsdWUgb2YgdGhlIGNhcGFjaXR5IGFzCgkvLyBzb29uIGFzIHRoZSB2YWx1ZSBvZiBjYXBhY2l0eSBiZWNvbWVzIG5lZ2F0aXZlIHNvIGFzCgkvLyBub3QgdG8gdHJhdmVyc2UgdGhlIGFycmF5IHR3aWNlIGluIG9yZGVyIHRvIGdldCB0aGUKCS8vIHNvbHV0aW9uCglpbnQgc3RhcnQgPSAwLCBkZWZpY2l0ID0gMDsKCWludCBjYXBhY2l0eSA9IDA7Cglmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewoJCWNhcGFjaXR5ICs9IHBbaV0ucGV0cm9sIC0gcFtpXS5kaXN0YW5jZTsKCQlpZiAoY2FwYWNpdHkgPCAwKSB7CgkJCS8vIElmIHRoaXMgcGFydGljdWxhciBzdGVwIGlzIG5vdCBkb25lIHRoZW4gdGhlCgkJCS8vIGJldHdlZW4gc3RlcHMgd291bGQgYmUgcmVkdW5kYW50CgkJCXN0YXJ0ID0gaSArIDE7CgkJCWRlZmljaXQgKz0gY2FwYWNpdHk7CgkJCWNhcGFjaXR5ID0gMDsKCQl9Cgl9CglyZXR1cm4gKGNhcGFjaXR5ICsgZGVmaWNpdCA+PSAwKSA/IHN0YXJ0IDogLTE7Cn0KLy8gRHJpdmVyIGNvZGUKaW50IG1haW4oKQp7CnBldHJvbFB1bXAgYXJyW10gPSB7ezMsIH0sIHsgNiwgNCB9LCB7IDMsIDYgfSwgeyA3LCAzIH0gfTsKCglpbnQgbiA9IHNpemVvZihhcnIpIC8gc2l6ZW9mKGFyclswXSk7CglpbnQgc3RhcnQgPSBwcmludFRvdXIoYXJyLCBuKTsKCgkoc3RhcnQgPT0gLTEpID8gY291dCA8PCAiTm8gc29sdXRpb24iCgkJCQk6IGNvdXQgPDwgIlN0YXJ0ID0gIiA8PCBzdGFydDsKCglyZXR1cm4gMDsKfQoKLy8gVGhpcyBjb2RlIGlzIGNvbnRyaWJ1dGVkIGJ5IGFkaXR5YSBrdW1hcgo=