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