2015
04-16

# Random Sequence

There is a random sequence L whose element are all random numbers either -1 or 1 with the same possibility. Now we define MAVS, the abbreviate of Maximum Absolute Value Subsequence, to be any (if more than one) subsequences of L whose absolute value is maximum among all subsequences. Given the length of L, your task is to find the expectation of the absolute value of MAVS.

There is only one input file. The first line is the number of test cases T. T positive integers follow, each of which contains one positive number not greater than 1500 denoted the length of L.

There is only one input file. The first line is the number of test cases T. T positive integers follow, each of which contains one positive number not greater than 1500 denoted the length of L.

3
1
5
10

Case 1: 1.000000
Case 2: 2.750000
Case 3: 4.167969

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <sstream>
#include <fstream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
#define swap(t,x,y) (t=x,x=y,y=t)
#define distance(x1,x2,y1,y2,z1,z2) (sqrt(pow(x2-x1,2)+pow(y2-y1,2)+pow(z2-z1,2)))
#define myabs(x) (x<0?-x:x)
#define sgn(x) (x<0?-1:(x>0?1:0))
#define clr(list) memset(list,0,sizeof(list))

using namespace std;

double ans[1540];

int main()
{
double x=1.0;
ans[1]=1.0;
for (int i=2;i<=1500;i++)
{
if (i%2==0)
x=x*(i-1.0)/(i*1.0);
ans[i]=ans[i-1]+x;
}
int t;
int cas=0;
scanf("%d",&t);
while (t--)
{
int n;
scanf("%d",&n);
printf("Case %d: %.6lf\n",++cas,ans[n]);
}
return 0;
}

1. 我看这个有段时间了 就一直没更 ！！！！作者你既然要发表这漫画，就得满足我们这些粉丝啊！！！老是不更新 ，，叫我们这些想看的怎么看你！！

2. 我看这个有段时间了 就一直没更 ！！！！作者你既然要发表这漫画，就得满足我们这些粉丝啊！！！老是不更新 ，，叫我们这些想看的怎么看你！！

3. 我看这个有段时间了 就一直没更 ！！！！作者你既然要发表这漫画，就得满足我们这些粉丝啊！！！老是不更新 ，，叫我们这些想看的怎么看你！！

4. 我看这个有段时间了 就一直没更 ！！！！作者你既然要发表这漫画，就得满足我们这些粉丝啊！！！老是不更新 ，，叫我们这些想看的怎么看你！！

5. 我看这个有段时间了 就一直没更 ！！！！作者你既然要发表这漫画，就得满足我们这些粉丝啊！！！老是不更新 ，，叫我们这些想看的怎么看你！！

6. 我看这个有段时间了 就一直没更 ！！！！作者你既然要发表这漫画，就得满足我们这些粉丝啊！！！老是不更新 ，，叫我们这些想看的怎么看你！！

7. 我看这个有段时间了 就一直没更 ！！！！作者你既然要发表这漫画，就得满足我们这些粉丝啊！！！老是不更新 ，，叫我们这些想看的怎么看你！！

8. 我看这个有段时间了 就一直没更 ！！！！作者你既然要发表这漫画，就得满足我们这些粉丝啊！！！老是不更新 ，，叫我们这些想看的怎么看你！！

9. 总有人自以为是的乱带节奏 自己不喜欢吃或周围一两个人不喜欢 就各种南方人 北方人 现在大家都天南海北的到处跑 哪还有那么多地域之分？

10. 总有人自以为是的乱带节奏 自己不喜欢吃或周围一两个人不喜欢 就各种南方人 北方人 现在大家都天南海北的到处跑 哪还有那么多地域之分？

11. 总有人自以为是的乱带节奏 自己不喜欢吃或周围一两个人不喜欢 就各种南方人 北方人 现在大家都天南海北的到处跑 哪还有那么多地域之分？

12. 总有人自以为是的乱带节奏 自己不喜欢吃或周围一两个人不喜欢 就各种南方人 北方人 现在大家都天南海北的到处跑 哪还有那么多地域之分？

13. 总有人自以为是的乱带节奏 自己不喜欢吃或周围一两个人不喜欢 就各种南方人 北方人 现在大家都天南海北的到处跑 哪还有那么多地域之分？

14. 总有人自以为是的乱带节奏 自己不喜欢吃或周围一两个人不喜欢 就各种南方人 北方人 现在大家都天南海北的到处跑 哪还有那么多地域之分？

15. 总有人自以为是的乱带节奏 自己不喜欢吃或周围一两个人不喜欢 就各种南方人 北方人 现在大家都天南海北的到处跑 哪还有那么多地域之分？

16. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;