7-8 ladder cloud vertical

7-8 Echelon of clouds

After Newton announced that the Chinese film and television city was not under his control , cross * Tiyunzong can take off in situ and go straight to the moon . Suppose horizontal * It's only... From the moon n rice , And horizontal * A slow motion with the left foot and the right foot can increase the probability 1 rice perhaps 2 rice . Please calculate his steps to the moon .
Be careful , When he was only... Away from the moon 1 Rice is , He will 100% The probability of choice rises 1 rice .
set up X The probability of walking to the moon P(X) by , The number of steps to land on the moon is expected =∑ X=0n P(X)∗X
Input format :
In the first line, enter the number of sample groups t(1<=t<=100)
After that t That's ok , Each line gives a positive integer n(1<=n<=10 5) Indicates horizontal * The moon has n rice

Output format :
For each set of data , Output the expected number of steps to the moon in one line , Rounding reservation 6 Decimal place .

sample input :
Here's a set of inputs . for example ：

3
1
2
3

sample output :
Here is the corresponding output . for example ：

1.000000
1.500000
2.250000

Code ：

#include <stdio.h>
#include <stdlib.h>
#include<math.h>
int n;
double a[110000];
double mid[110000];
double getmid(int x)// Return difference 
{
    
    if(mid[x]!=0)
        return mid[x];
    else
        return mid[x]=(getmid(x-1)+getmid(x-2))/2;
}
double geta(int x)
{
    
    if(a[x]!=0)
        return a[x];
    else
        return a[x]=geta(x-1)+getmid(x-1);
}
double change(double x)
{
    
    if(x<10000)
        return x;
    return x+0.0000002;
}
int main()
{
    
    scanf("%d",&n);
    int x;

    a[0]=0;
    a[1]=1;
    a[2]=1.5;
    a[3]=2.25;
    //a[4]=2.875;
    mid[0]=a[1]-a[0];
    mid[1]=a[2]-a[1];
    mid[2]=a[3]-a[2];
    //mid[3]=a[4]-a[3];
    for(int i=0;i<n;i++)
    {
    
        scanf("%d",&x);
        double z=geta(x);
        printf("%lf\n",change(z));
    }
    return 0;
}

Tips :
20% The data of ,1<=n<=10
40% The data of ,1<=n<=10 2
60% The data of ,1<=n<=10 4
100% The data of ,1<=n<=10 5

202206222107 3、 ... and