QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#153009 | #6829. It Takes Two of Two | qzez# | WA | 2ms | 5880kb | C++14 | 1.7kb | 2023-08-29 08:34:08 | 2023-08-29 08:34:10 |
Judging History
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'