BEGGASOL - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Ildar Gainullin
Tester: Nikolay Budin
Editorialist: Alei Reyes

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

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();
  }
}

VIDEO EDITORIAL (Hindi):

VIDEO EDITORIAL (English):

7 Likes
int a = f[0];
            int dist = 0;
            for (int i = 1; i < n; i++) {
                a--;
                a += f[i];
                dist++;

                if (a == 0) {
                    break;
                }
            }

            if (a > 0) {
                dist += a;
            }

can anybody tell me what’s wrong here?

what is wrong with this solution

Blockquote

#include<bits/stdc++.h>
using namespace std;
/*
do not voilate rules
*/
void fastio()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}

int main()
{
fastio();
int t;//number of testcase
cin>>t;
while(t–)
{
int n;
cin>>n;

   int arr[n];
   
  for(int i=0;i<n;i++)
    cin>>arr[i];
  
  
   int count=0;
   for(int i=1;i<=n-1;i++)
   {
     if(arr[i-1]-1>=0)
     {
      count++;     
      arr[i]=arr[i-1]-1+arr[i];
     }
     else
     break;
   }
   
  cout<<arr[n-1]+count<<endl;     
}

}

@a3000 @tiwary123

Test case

1
2
0 10

Expected Output

0

what about my sol

//#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;
}


		
	}
	
}

@akshay_012

Test case

1
4
1 1 0 10

Expected Output

2

1 Like

i am never going to drive in my life.
good problem though.

3 Likes

Can anybody Tellme what’s wrong in my solution?
https://www.codechef.com/viewsolution/39895798

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?

1 Like

Yes, the intuition is right maybe you got ur implementation wrong…
Check if you reduced fuel after every unit travel.

Why is this showing Segmentation Fault ???

Note: I’m new to the platform.

   #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;
}

what is the problrm in this code? can you guys help me out :slight_smile:
this is my code:-

https://www.codechef.com/viewsolution/39935848

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!!!

Why my code is not able to clear subtask. Please check my code and tell me what mistake I am doing

#include

using namespace std;

int main(){

int T;

cin>>T;

while(T–){

int n;

cin>>n;

int car[n];

int g=0,d=0;

for(int i=0;i<n;i++){

    cin>>car[i];        

}

for(int i=0;i<n;i++){

    g+=car[i];

    if(g==0){

        break;

    }

    g--;

    d++;

}

cout<<d+g;

}

return 0;

}

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”;

:sunny:Hope you understand this… :innocent:

`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.

link: https://www.codechef.com/viewsolution/39962838

Good to hear it @akjder_boy:innocent:

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)

Has anyone solved it successfully in java I am facing a problem? Can anyone help?