There are N cars in a circle, the i-th car has f_i units of gasoline. The distance between each pair of adjacent cars is one unit.
You are in the first car and keep driving clockwise, it takes you one unit of gasoline to move one unit of distance. Whenever you reach a new car, you steal all of its gasoline.
Find the maximum distance you can travel until your car gets out of gasoline.
QUICK EXPLANATION:
Simulate the process.
EXPLANATION:
Let G be the current amount of gasoline in our car, D the total distance we have traveled, and i the index of our current position in the circle.
Initially G=0, D=0 and i=1. The process goes as follows:
Steal the gasoline from the i-th car, i.e G increases by f_i.
If we are left whithout gasoline, the process finishes.
Otherwise, move to the next car clockwise: i increases by one, G decreases by one (we have to consume gasoline) and D increases by one (we travel an additional unit of distance).
We have to repeat the previous process at most N times (one full circle), after that each car will be visited at most once and no more gasoline can be stealed. To keep moving we have to consume all the remaining G units of gasoline and travel an additional G units of distance.
SOLUTIONS:
Setter's Solution
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector <int> f(n);
for (int i = 0; i < n; i++) {
cin >> f[i];
}
int cur = 0;
int ans = 0;
int i = 0;
while (true) {
cur += f[i];
f[i] = 0;
if (cur >= 1) {
ans++;
cur--;
i++;
if (i >= n) i -= n;
} else {
break;
}
}
cout << ans << '\n';
}
}
Tester's Solution
void solve() {
int n;
cin >> n;
vector<int> arr;
for (int i = 0; i < n; ++i) {
int num;
cin >> num;
arr.push_back(num);
}
int ans = 0;
int left = 0;
for (int i = 0; i < n; ++i) {
left += arr[i];
if (left == 0) {
cout << ans << "\n";
return;
}
left--;
ans++;
}
ans += left;
cout << ans << "\n";
}
int main() {
int test_count = 1;
cin >> test_count;
for (int test = 1; test <= test_count; ++test) {
solve();
}
}
//#include <sstream>
using namespace std;
int main()
{
long long int t=0;
cin>>t;
while(t--)
{
long long int n=0;
cin>>n;
long long int a[101]={0};
for(int i=0; i<n; i++)
cin>>a[i];
long long int sum=0,sum1=0;
if(a[0]==0)
cout<<"0"<<endl;
else
{
for(int i=0; i<n; i++){
sum+=a[i];
sum1+=a[i];
// cout<<sum1<<endl;
if(a[i]==0){
sum1--;
if(sum1<=0)
break; }
}
cout<<sum<<endl;
}
}
}
On solving the problem mathematically you can see that the maximum distance car1 will travel before it runs out of gasoline will be sum of gasoline array. I implemented this but still got WA, anybody knows why?
#include <iostream>
using namespace std;
int
main ()
{
int T;
int N;
//int f[10];
scanf("%d", &T) ;
for (int j = 0; j < T; j++)
{
int f[10];
scanf("%d", &N) ;
for (int i = 0; i < N; i++)
{
scanf("%d", &f[i]) ;
}
int gas;
gas = f[0];
int distance = 0;
for( int i = 1 ; i < N ; i++)
{
if ( gas == 0)
break;
gas = gas - 1 + f[i];
distance++;
}
int ans = distance + gas;
printf("%d", ans ) ;
}
return 0;
}
also if the link is not working :-
#include<bits/stdc++.h> #define lli long long int
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int testcase;
cin>>testcase;
int arr[100];
while(testcase--)
{
bool flag = false;
int n;
cin>>n;
for(int i=0;i!=n;i++)
{
cin>>arr[i];
}
int maincounter = arr[0];
int counter = 0;
//equating for the first loop differently
if(maincounter!=0)
{
for(int i=1;i!=n;i++)
{
maincounter = maincounter - 1 + arr[i];
if(maincounter == 0)
{
counter++;
bool flag = true;
break;
}
counter++;
}
}
//this case stand for either the vehicle broke down in the first loop for not
if(flag)
cout<<counter<<"\n";
else
cout<<counter + maincounter<<"\n";
}
return 0;
}
please let me know what exactly went wrong … thank you!!!
You have declared ’ f ’ array to be of constant size 10 but it can be more than 10 also in the test cases i.e., it can be upto 100 as per the given problem 1 <=N<=100 And also logic inside for loop isn’t correct completly…
You cannot break out when just gas == 0 because consider the fuel array to be 2 0 1 1 1 1 here you take the fuel of car 0 and you go to car1 so fuel becomes 1 and you move to car2 fuel becomes 0 but you can still steal the fuel from car2. But your code breaks the loop here itself…
Try this
int totalFuel = 0;
for(int i = 0;i<n;i++){
totalFuel = totalFuel + f[i];
//now after stealing the fuel check if fuel is == 0
if(totalFuel == 0)break;
totalFuel --; //consume 1 unit fuel before reaching next car
}
//check if it broke the loop in between
if(i != n)cout << i << “\n”;
//otherwise distance will be f array size plus fuel left_out
else cout << n + totalFuel << “\n”;
`You have declared the 'f ' array to be of constant size 10 but it can be more than 10 also in the test cases i.e., it can be up to 100 as per the given problem 1 <=N<=100 And also logic inside for loop isn’t correct completely…`
This was my only mistake. Thanks for helping me, keeru_123!
My Solution got 100% accepted.
In this code, i can’t seem to find any problem in it, but after submission, it still shows the wrong answer
for _ in range(int(input())):
n = int(input())
f = list(map(int, input().split()))
g = f[0]
step = 0
for i in range(1,n):
g += f[i]
g -= 1
step += 1
if g==0:
break
step += g
print(step)