注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2489]Random Sequence  

2015-06-20 16:14:25|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2489: Random Sequence

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 129  Solved: 31
[Submit][Status][Discuss]

Description

给你一个数字L,代表数字串长。这个数字串每个元素为1或-1.

那么就有这个数列有2^L种可能。

现对每个可能的数字串,求其连续子串和,并将和取绝对值,记下最大的那个值。

再求出所有这些值的总和。

输入总和/2^L

Input

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. 

Output

For each test case, output the expectation you are required to calculate. Answers are rounded to 6 numbers after the decimal point.(as shown in the sample output)

Sample Input

3 1 5 10

Sample Output

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

HINT

当输入2时,有

1 1

1 -1

-1 1

-1 -1

这四种可能,其对应的值分别为(2+1+1+2)=6

6/4=1.5

Source

Solution

找规律大法好
交上去秒wa。。。然后要了数据只有一组1~1500,在(n=11?)的时候跪了,原因是因为x.499999和x.500000。。。。。。

Code

/**************************************************************
    Problem: 2489
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:4 ms
    Memory:816 kb
****************************************************************/
 
#include<cstdio>
double a[1510],x;int k,n,t;main(){
    for(a[1]=x=1,n=2;n<=1500;a[n]=a[n-1]+x,n++)if(~n&1)x=x*(n-1)/n;
    for(scanf("%d",&t);t--;scanf("%d",&n),printf("Case %d: %lf\n",++k,a[n]+1e-10));
}
  评论这张
 
阅读(42)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018