QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#153009#6829. It Takes Two of Twoqzez#WA 2ms5880kbC++141.7kb2023-08-29 08:34:082023-08-29 08:34:10

Judging History

你现在查看的是最新测评结果

  • [2023-08-29 08:34:10]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5880kb
  • [2023-08-29 08:34:08]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=200+5,M=100+5,K=600+5,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
int n;db dp[N][N/2][N/3][N/3];
void Solve(){
	int i,j,h,s,k;
	scanf("%d",&n);
	if(n==1){puts("0.00000000");return;}
	dp[n][0][0][0]=1;
	db ans=0;
	for(j=n;~j;j--){
		for(i=(n-j)/2;~i;i--){
			for(k=(n-j-2*i)/3;~k;k--){
				for(h=(n-j-2*i-3*k)/3;~h;h--) {
					db p=(2*k*(2*k-2)+2*k+2*i*(2*i-2)+j*(j-1)+2*k*2*i*2+(2*i+2*k)*j*2)*1.0/n/n;
					if(!p) continue;
					ans+=1/p*dp[j][i][k][h];
					// cerr<<j<<' '<<i<<' '<<k<<' '<<h<<' '<<dp[j][i][k][h]<<' '<<p<<'\n';
					p=2*k*(2*k-2)+2*k+2*i*(2*i-2)+j*(j-1)+2*k*2*i*2+(2*i+2*k)*j*2;
					if(k) dp[j][i][k-1][h+1]+=dp[j][i][k][h]*2*k/p;
					if(k>1) dp[j][i][k-1][h]+=dp[j][i][k][h]*2*k*(2*k-2)/p;
					if(i>1) dp[j][i-2][k+1][h]+=dp[j][i][k][h]*2*i*(2*i-2)*2/p;
					if(j>1) dp[j-2][i+1][k][h]+=dp[j][i][k][h]*j*(j-1)/p;
					if(k&&i) dp[j][i-1][k][h]+=dp[j][i][k][h]*2*i*2*k*2/p;
					if(j&&i) dp[j-1][i-1][k+1][h]+=dp[j][i][k][h]*2*j*2*i/p;
					if(j&&k) dp[j-1][i][k][h]+=dp[j][i][k][h]*2*j*2*k/p;
				}
			}
		}
	}
	printf("%.8lf\n",ans);
}
int main(){
	int t;
	// scanf("%d",&t);
	t=1;
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3820kb

input:

1

output:

0.00000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 5868kb

input:

2

output:

2.00000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 5864kb

input:

3

output:

8.25000000

result:

ok found '8.2500000', expected '8.2500000', error '0.0000000'

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 5880kb

input:

4

output:

12.93333333

result:

wrong answer 1st numbers differ - expected: '11.3333333', found: '12.9333333', error = '0.1411765'