Let suppose N cars are parked on a circular track**(1 to N)** at distance of 1km each. Each car contains some fuels (Fi to Fn).A car runs 2km per litre of fuel. You are driving car 1 in the clockwise direction. To move one unit of distance in this direction, you need to spend half litre of gasoline. When you pass another car parked at even position (even if you'd run out of gasoline exactly at that point), you steal all its gasoline and When you pass another car parked at odd position,you steal half of its gasoline each time. Once you do not have any gasoline left, you stop.
Here is one catch that you will not steal gasoline from other cars if that car has less then 2 litres of gasoline.
What is the total clockwise distance travelled by your car?
Input Format
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 N.
The second line contains N space-separated integers f1,f2,…,fN.
Constraints
1≤ T ≤100
1≤ N ≤100
0≤ fi ≤100
Output Format
Total distance traveled for each test cases into seperated line.
Sample Input 0
2
5
1 2 3 4 5
6
2 5 2 0 1 0
Sample Output 0
24.5
16
Answers
Answer:
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
int t,j,k,n,i;
double d,x;
Scanner sc=new Scanner(System.in);
t=sc.nextInt();
Solution in=new Solution();
for(i=0;i<t;i++)
{
n=sc.nextInt();
if(n>1)
{
double a[]=new double[n];
for(j=0;j<n;j++)
{
a[j]=sc.nextInt();
}
k=1;
d=0.0;
x=a[0];
if(x==0)
{
d=0;
}
while(x>0)
{
if(a[k]>=2)
{
if((k+1)%2==0)
{
x=x+a[k];
a[k]=0;
}
if((k+1)%2!=0)
{
x=x+a[k]/2.0;
a[k]=a[k]/2.0;
}
}
if(x>=0.5)
{
d++;
x=x-0.5;
}
else
{
d=d+(x*2);
x=0;
}
if(k==(a.length-1))
{
k=1;
}
else
k++;
}
if(d%1!=0)
System.out.println(" "+d);
else
System.out.println(" "+(int)d);
}
else
{
int l=sc.nextInt();
d=l*2;
System.out.println("0");
}
}
}
}