@[chen_zhe](/space/show?uid=8457) .
by 久远寺有珠 @ 2018-10-12 19:50:22
而且题意也有误,根据测试数据来看应该是246到队尾,35出队
by 久远寺有珠 @ 2018-10-12 19:57:23
@[chen_zhe](/space/show?uid=8457)
by hanjicheng @ 2018-10-17 16:41:09
```cpp
//70wa
#include<iostream>
#include<cmath>
#include<memory.h>
#include<cstdio>
using namespace std;
int n,m;
double dp[1001];
double p[1001];
double ans=0;
void F()
{
double all=1.0/3.0;
dp[1]=1;
p[1]=1.0/3.0;
for(int i=2;i<=n;i++)
{
//cout<<"i="<<i<<endl;
double w=1.0/6.0;
for(int j=1;j<i;j++)
{
p[j]*=i-1;
p[j]/=2;
p[j]/=i-j;
w+=p[j]*dp[j];
}
//cout<<"w="<<w<<" ";
p[i]=all/=3;
//cout<<"all="<<all<<endl;
//dp[i]=w;
dp[i]=w/(1-all);/////////////////////////////////////////////////////////////////////
//cout<<endl<<"dp[i]="<<dp[i]<<endl;
//cout<<dp[i]<<endl;
//w(n)=1/6+(1/2)^k*(1/3)^(n-k)*c(n-1,k)*dp(n-k) (k=1~n-1);
//dp(n)=w(n)*(1+(1/3)^(n)+(1/3)^(2n)+(1/3)^(3n)+……)
}
return;
}
int main()
{
cin>>n>>m;
F();
//cout<<c[60][30]<<endl<<c[1000][500]<<endl;
memset(p,0,sizeof(p));
p[n-m+1]=1.0;
int j=0;
for(int i=1;i<m;i++) p[n-m+1]/=2;
ans=p[n-m+1]*dp[n-m+1];
for(int i=n-m+2;i<=n;i++)//剩下了的人数
{
j++;
p[i]=p[i-1]*2*(m-j)/3/j;
//cout<<"p[i]="<<p[i]<<endl;
ans+=p[i]*dp[i];
//cout<<ans<<endl;
}
//cout<<p[1]<<" "<<p[2]<<" "<<p[3]<<endl;
//cout<<endl<<dp[n]<<endl;
//printf("%.9Lf",dp[n]);
printf("%.9lf",ans);
return 0;
}
```
```cpp
//100ac 把所有3改为2,所有2改为3
#include<iostream>
#include<cmath>
#include<memory.h>
#include<cstdio>
using namespace std;
int n,m;
double dp[1001];
double p[1001];
double ans=0;
void F()
{
double all=1.0/2.0;
dp[1]=1;
p[1]=1.0/2.0;
for(int i=2;i<=n;i++)
{
//cout<<"i="<<i<<endl;
double w=1.0/6.0;
for(int j=1;j<i;j++)
{
p[j]*=i-1;
p[j]/=3;
p[j]/=i-j;
w+=p[j]*dp[j];
}
//cout<<"w="<<w<<" ";
p[i]=all/=2;
//cout<<"all="<<all<<endl;
//dp[i]=w;
dp[i]=w/(1-all);/////////////////////////////////////////////////////////////////////
//cout<<endl<<"dp[i]="<<dp[i]<<endl;
//cout<<dp[i]<<endl;
//w(n)=1/6+(1/2)^k*(1/3)^(n-k)*c(n-1,k)*dp(n-k) (k=1~n-1);
//dp(n)=w(n)*(1+(1/3)^(n)+(1/3)^(2n)+(1/3)^(3n)+……)
}
return;
}
int main()
{
cin>>n>>m;
F();
//cout<<c[60][30]<<endl<<c[1000][500]<<endl;
memset(p,0,sizeof(p));
p[n-m+1]=1.0;
int j=0;
for(int i=1;i<m;i++) p[n-m+1]/=3;
ans=p[n-m+1]*dp[n-m+1];
for(int i=n-m+2;i<=n;i++)//剩下了的人数
{
j++;
p[i]=p[i-1]*3*(m-j)/2/j;
//cout<<"p[i]="<<p[i]<<endl;
ans+=p[i]*dp[i];
//cout<<ans<<endl;
}
//cout<<p[1]<<" "<<p[2]<<" "<<p[3]<<endl;
//cout<<endl<<dp[n]<<endl;
//printf("%.9Lf",dp[n]);
printf("%.9lf",ans);
return 0;
}
```
by hanjicheng @ 2018-10-17 16:42:36
谢谢x
by Uranus @ 2018-11-19 15:47:57