Gasoline Introduction [BEGGASOL](Solution)

Question

There are N cars (numbered 1 through N) on a circular track with length N. For each i (2≤i≤N), the i-th of them is at a distance i−1 clockwise from car 1, i.e. car 1 needs to travel a distance i−1 clockwise to reach car ii. Also, for each valid ii, the i-th car has fi liters of gasoline in it initially.

You are driving car 1 in the clockwise direction. To move one unit of distance in this direction, you need to spend 1 liter of gasoline. When you pass another car (even if you’d run out of gasoline exactly at that point), you steal all its gasoline. Once you do not have any gasoline left, you stop.

What is the total clockwise distance traveled by your car?

Input

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains a single integer NN.
• The second line contains NN space-separated integers f1,f2,…,fN

Output

For each test case, print a single line containing one integer ― the total clockwise distance traveled.

Constraints

• 1≤T≤100
• 1≤N≤100
• 0≤fi≤100 for each valid i

Subtasks

Subtask #1 (100 points): original constraints

Example Input

3
5
3 0 0 0 0
5
1 1 1 1 1
5
5 4 3 2 1

Example Output

3
5
15

Solution

#include <iostream>
using namespace std;
int
main ()
{
int T;
 int N;
 int f[100];
 
 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 \n”, ans ) ;
 }
 return 0;
}

This solution is Just for the understanding of logic after the contest is over. In no way I urge you to cheat in the contest. Remember these challenges are only for learning.

Let’s grab a coffee on Instagram: decaf_dope

Question Link

Contest Page | CodeChef