QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#153016 | #6829. It Takes Two of Two | qzez# | AC ✓ | 42ms | 164876kb | C++14 | 1.7kb | 2023-08-29 08:47:21 | 2023-08-29 08:47:22 |
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--) if(dp[j][i][k][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];
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;
// cerr<<j<<' '<<i<<' '<<k<<' '<<h<<' '<<dp[j][i][k][h]<<' '<<p<<' '<<dp[0][0][1][0]<<'\n';
if(i>1) dp[j][i-2][k+1][h]+=dp[j][i][k][h]*2*i*(2*i-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';
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3748kb
input:
1
output:
0.00000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 5884kb
input:
2
output:
2.00000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5784kb
input:
3
output:
8.25000000
result:
ok found '8.2500000', expected '8.2500000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 5944kb
input:
4
output:
11.33333333
result:
ok found '11.3333333', expected '11.3333333', error '0.0000000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 5832kb
input:
5
output:
17.04861111
result:
ok found '17.0486111', expected '17.0486111', error '0.0000000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 5956kb
input:
6
output:
26.03406593
result:
ok found '26.0340659', expected '26.0340659', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5908kb
input:
7
output:
35.49756260
result:
ok found '35.4975626', expected '35.4975626', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 5944kb
input:
8
output:
46.22930531
result:
ok found '46.2293053', expected '46.2293053', error '0.0000000'
Test #9:
score: 0
Accepted
time: 2ms
memory: 5936kb
input:
9
output:
58.61439635
result:
ok found '58.6143963', expected '58.6143964', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 5872kb
input:
10
output:
72.43776842
result:
ok found '72.4377684', expected '72.4377684', error '0.0000000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 5988kb
input:
11
output:
87.67879666
result:
ok found '87.6787967', expected '87.6787967', error '0.0000000'
Test #12:
score: 0
Accepted
time: 2ms
memory: 6020kb
input:
12
output:
104.36131898
result:
ok found '104.3613190', expected '104.3613190', error '0.0000000'
Test #13:
score: 0
Accepted
time: 2ms
memory: 6072kb
input:
13
output:
122.48185932
result:
ok found '122.4818593', expected '122.4818593', error '0.0000000'
Test #14:
score: 0
Accepted
time: 1ms
memory: 6152kb
input:
14
output:
142.03652436
result:
ok found '142.0365244', expected '142.0365244', error '0.0000000'
Test #15:
score: 0
Accepted
time: 1ms
memory: 6040kb
input:
15
output:
163.02399178
result:
ok found '163.0239918', expected '163.0239918', error '0.0000000'
Test #16:
score: 0
Accepted
time: 2ms
memory: 6116kb
input:
16
output:
185.44294196
result:
ok found '185.4429420', expected '185.4429420', error '0.0000000'
Test #17:
score: 0
Accepted
time: 2ms
memory: 6232kb
input:
17
output:
209.29206457
result:
ok found '209.2920646', expected '209.2920646', error '0.0000000'
Test #18:
score: 0
Accepted
time: 2ms
memory: 6256kb
input:
18
output:
234.57019534
result:
ok found '234.5701953', expected '234.5701953', error '0.0000000'
Test #19:
score: 0
Accepted
time: 2ms
memory: 6384kb
input:
19
output:
261.27628211
result:
ok found '261.2762821', expected '261.2762821', error '0.0000000'
Test #20:
score: 0
Accepted
time: 2ms
memory: 6276kb
input:
20
output:
289.40936221
result:
ok found '289.4093622', expected '289.4093622', error '0.0000000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 6340kb
input:
21
output:
318.96855141
result:
ok found '318.9685514', expected '318.9685514', error '0.0000000'
Test #22:
score: 0
Accepted
time: 2ms
memory: 6500kb
input:
22
output:
349.95303412
result:
ok found '349.9530341', expected '349.9530341', error '0.0000000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 6480kb
input:
23
output:
382.36205492
result:
ok found '382.3620549', expected '382.3620549', error '0.0000000'
Test #24:
score: 0
Accepted
time: 2ms
memory: 6616kb
input:
24
output:
416.19491154
result:
ok found '416.1949115', expected '416.1949115', error '0.0000000'
Test #25:
score: 0
Accepted
time: 0ms
memory: 6680kb
input:
25
output:
451.45094892
result:
ok found '451.4509489', expected '451.4509489', error '0.0000000'
Test #26:
score: 0
Accepted
time: 0ms
memory: 6716kb
input:
26
output:
488.12955416
result:
ok found '488.1295542', expected '488.1295542', error '0.0000000'
Test #27:
score: 0
Accepted
time: 1ms
memory: 6948kb
input:
27
output:
526.23015219
result:
ok found '526.2301522', expected '526.2301522', error '0.0000000'
Test #28:
score: 0
Accepted
time: 1ms
memory: 6884kb
input:
28
output:
565.75220204
result:
ok found '565.7522020', expected '565.7522020', error '0.0000000'
Test #29:
score: 0
Accepted
time: 3ms
memory: 7016kb
input:
29
output:
606.69519356
result:
ok found '606.6951936', expected '606.6951936', error '0.0000000'
Test #30:
score: 0
Accepted
time: 3ms
memory: 7164kb
input:
30
output:
649.05864468
result:
ok found '649.0586447', expected '649.0586447', error '0.0000000'
Test #31:
score: 0
Accepted
time: 2ms
memory: 7352kb
input:
31
output:
692.84209882
result:
ok found '692.8420988', expected '692.8420988', error '0.0000000'
Test #32:
score: 0
Accepted
time: 2ms
memory: 7384kb
input:
32
output:
738.04512282
result:
ok found '738.0451228', expected '738.0451228', error '0.0000000'
Test #33:
score: 0
Accepted
time: 3ms
memory: 7460kb
input:
33
output:
784.66730490
result:
ok found '784.6673049', expected '784.6673049', error '0.0000000'
Test #34:
score: 0
Accepted
time: 3ms
memory: 7620kb
input:
34
output:
832.70825303
result:
ok found '832.7082530', expected '832.7082530', error '0.0000000'
Test #35:
score: 0
Accepted
time: 0ms
memory: 7776kb
input:
35
output:
882.16759336
result:
ok found '882.1675934', expected '882.1675934', error '0.0000000'
Test #36:
score: 0
Accepted
time: 3ms
memory: 7820kb
input:
36
output:
933.04496885
result:
ok found '933.0449689', expected '933.0449689', error '0.0000000'
Test #37:
score: 0
Accepted
time: 3ms
memory: 8080kb
input:
37
output:
985.34003806
result:
ok found '985.3400381', expected '985.3400381', error '0.0000000'
Test #38:
score: 0
Accepted
time: 3ms
memory: 8096kb
input:
38
output:
1039.05247402
result:
ok found '1039.0524740', expected '1039.0524740', error '0.0000000'
Test #39:
score: 0
Accepted
time: 0ms
memory: 8192kb
input:
39
output:
1094.18196325
result:
ok found '1094.1819633', expected '1094.1819632', error '0.0000000'
Test #40:
score: 0
Accepted
time: 1ms
memory: 8388kb
input:
40
output:
1150.72820482
result:
ok found '1150.7282048', expected '1150.7282048', error '0.0000000'
Test #41:
score: 0
Accepted
time: 3ms
memory: 8588kb
input:
41
output:
1208.69090958
result:
ok found '1208.6909096', expected '1208.6909096', error '0.0000000'
Test #42:
score: 0
Accepted
time: 4ms
memory: 8752kb
input:
42
output:
1268.06979936
result:
ok found '1268.0697994', expected '1268.0697994', error '0.0000000'
Test #43:
score: 0
Accepted
time: 0ms
memory: 8976kb
input:
43
output:
1328.86460631
result:
ok found '1328.8646063', expected '1328.8646063', error '0.0000000'
Test #44:
score: 0
Accepted
time: 1ms
memory: 9104kb
input:
44
output:
1391.07507226
result:
ok found '1391.0750723', expected '1391.0750723', error '0.0000000'
Test #45:
score: 0
Accepted
time: 4ms
memory: 9276kb
input:
45
output:
1454.70094817
result:
ok found '1454.7009482', expected '1454.7009482', error '0.0000000'
Test #46:
score: 0
Accepted
time: 3ms
memory: 9468kb
input:
46
output:
1519.74199356
result:
ok found '1519.7419936', expected '1519.7419936', error '0.0000000'
Test #47:
score: 0
Accepted
time: 1ms
memory: 9608kb
input:
47
output:
1586.19797607
result:
ok found '1586.1979761', expected '1586.1979761', error '0.0000000'
Test #48:
score: 0
Accepted
time: 1ms
memory: 9816kb
input:
48
output:
1654.06867098
result:
ok found '1654.0686710', expected '1654.0686710', error '0.0000000'
Test #49:
score: 0
Accepted
time: 1ms
memory: 10056kb
input:
49
output:
1723.35386080
result:
ok found '1723.3538608', expected '1723.3538608', error '0.0000000'
Test #50:
score: 0
Accepted
time: 1ms
memory: 10184kb
input:
50
output:
1794.05333491
result:
ok found '1794.0533349', expected '1794.0533349', error '0.0000000'
Test #51:
score: 0
Accepted
time: 0ms
memory: 10440kb
input:
51
output:
1866.16688916
result:
ok found '1866.1668892', expected '1866.1668892', error '0.0000000'
Test #52:
score: 0
Accepted
time: 1ms
memory: 10712kb
input:
52
output:
1939.69432558
result:
ok found '1939.6943256', expected '1939.6943256', error '0.0000000'
Test #53:
score: 0
Accepted
time: 17ms
memory: 82648kb
input:
153
output:
16628.00267053
result:
ok found '16628.0026705', expected '16628.0026705', error '0.0000000'
Test #54:
score: 0
Accepted
time: 11ms
memory: 83976kb
input:
154
output:
16845.20045860
result:
ok found '16845.2004586', expected '16845.2004586', error '0.0000000'
Test #55:
score: 0
Accepted
time: 21ms
memory: 85500kb
input:
155
output:
17063.80370767
result:
ok found '17063.8037077', expected '17063.8037077', error '0.0000000'
Test #56:
score: 0
Accepted
time: 15ms
memory: 86812kb
input:
156
output:
17283.81238040
result:
ok found '17283.8123804', expected '17283.8123804', error '0.0000000'
Test #57:
score: 0
Accepted
time: 11ms
memory: 88196kb
input:
157
output:
17505.22643977
result:
ok found '17505.2264398', expected '17505.2264398', error '0.0000000'
Test #58:
score: 0
Accepted
time: 12ms
memory: 89652kb
input:
158
output:
17728.04584913
result:
ok found '17728.0458491', expected '17728.0458491', error '0.0000000'
Test #59:
score: 0
Accepted
time: 11ms
memory: 91120kb
input:
159
output:
17952.27057215
result:
ok found '17952.2705721', expected '17952.2705722', error '0.0000000'
Test #60:
score: 0
Accepted
time: 11ms
memory: 92540kb
input:
160
output:
18177.90057284
result:
ok found '18177.9005728', expected '18177.9005728', error '0.0000000'
Test #61:
score: 0
Accepted
time: 12ms
memory: 94088kb
input:
161
output:
18404.93581552
result:
ok found '18404.9358155', expected '18404.9358155', error '0.0000000'
Test #62:
score: 0
Accepted
time: 8ms
memory: 95560kb
input:
162
output:
18633.37626486
result:
ok found '18633.3762649', expected '18633.3762649', error '0.0000000'
Test #63:
score: 0
Accepted
time: 33ms
memory: 96976kb
input:
163
output:
18863.22188582
result:
ok found '18863.2218858', expected '18863.2218858', error '0.0000000'
Test #64:
score: 0
Accepted
time: 11ms
memory: 98528kb
input:
164
output:
19094.47264370
result:
ok found '19094.4726437', expected '19094.4726437', error '0.0000000'
Test #65:
score: 0
Accepted
time: 17ms
memory: 100088kb
input:
165
output:
19327.12850407
result:
ok found '19327.1285041', expected '19327.1285041', error '0.0000000'
Test #66:
score: 0
Accepted
time: 8ms
memory: 101576kb
input:
166
output:
19561.18943285
result:
ok found '19561.1894328', expected '19561.1894328', error '0.0000000'
Test #67:
score: 0
Accepted
time: 16ms
memory: 103184kb
input:
167
output:
19796.65539621
result:
ok found '19796.6553962', expected '19796.6553962', error '0.0000000'
Test #68:
score: 0
Accepted
time: 21ms
memory: 104736kb
input:
168
output:
20033.52636065
result:
ok found '20033.5263607', expected '20033.5263606', error '0.0000000'
Test #69:
score: 0
Accepted
time: 20ms
memory: 106444kb
input:
169
output:
20271.80229293
result:
ok found '20271.8022929', expected '20271.8022929', error '0.0000000'
Test #70:
score: 0
Accepted
time: 16ms
memory: 108012kb
input:
170
output:
20511.48316014
result:
ok found '20511.4831601', expected '20511.4831601', error '0.0000000'
Test #71:
score: 0
Accepted
time: 20ms
memory: 109620kb
input:
171
output:
20752.56892959
result:
ok found '20752.5689296', expected '20752.5689296', error '0.0000000'
Test #72:
score: 0
Accepted
time: 31ms
memory: 111296kb
input:
172
output:
20995.05956892
result:
ok found '20995.0595689', expected '20995.0595689', error '0.0000000'
Test #73:
score: 0
Accepted
time: 24ms
memory: 112940kb
input:
173
output:
21238.95504602
result:
ok found '21238.9550460', expected '21238.9550460', error '0.0000000'
Test #74:
score: 0
Accepted
time: 32ms
memory: 114648kb
input:
174
output:
21484.25532904
result:
ok found '21484.2553290', expected '21484.2553290', error '0.0000000'
Test #75:
score: 0
Accepted
time: 19ms
memory: 116344kb
input:
175
output:
21730.96038641
result:
ok found '21730.9603864', expected '21730.9603864', error '0.0000000'
Test #76:
score: 0
Accepted
time: 30ms
memory: 118032kb
input:
176
output:
21979.07018681
result:
ok found '21979.0701868', expected '21979.0701868', error '0.0000000'
Test #77:
score: 0
Accepted
time: 21ms
memory: 119832kb
input:
177
output:
22228.58469920
result:
ok found '22228.5846992', expected '22228.5846992', error '0.0000000'
Test #78:
score: 0
Accepted
time: 16ms
memory: 121520kb
input:
178
output:
22479.50389277
result:
ok found '22479.5038928', expected '22479.5038928', error '0.0000000'
Test #79:
score: 0
Accepted
time: 12ms
memory: 123388kb
input:
179
output:
22731.82773697
result:
ok found '22731.8277370', expected '22731.8277370', error '0.0000000'
Test #80:
score: 0
Accepted
time: 19ms
memory: 125140kb
input:
180
output:
22985.55620149
result:
ok found '22985.5562015', expected '22985.5562015', error '0.0000000'
Test #81:
score: 0
Accepted
time: 37ms
memory: 126932kb
input:
181
output:
23240.68925627
result:
ok found '23240.6892563', expected '23240.6892563', error '0.0000000'
Test #82:
score: 0
Accepted
time: 20ms
memory: 128696kb
input:
182
output:
23497.22687150
result:
ok found '23497.2268715', expected '23497.2268715', error '0.0000000'
Test #83:
score: 0
Accepted
time: 4ms
memory: 130652kb
input:
183
output:
23755.16901758
result:
ok found '23755.1690176', expected '23755.1690176', error '0.0000000'
Test #84:
score: 0
Accepted
time: 33ms
memory: 132472kb
input:
184
output:
24014.51566517
result:
ok found '24014.5156652', expected '24014.5156652', error '0.0000000'
Test #85:
score: 0
Accepted
time: 23ms
memory: 134396kb
input:
185
output:
24275.26678514
result:
ok found '24275.2667851', expected '24275.2667851', error '0.0000000'
Test #86:
score: 0
Accepted
time: 33ms
memory: 136304kb
input:
186
output:
24537.42234861
result:
ok found '24537.4223486', expected '24537.4223486', error '0.0000000'
Test #87:
score: 0
Accepted
time: 20ms
memory: 138212kb
input:
187
output:
24800.98232691
result:
ok found '24800.9823269', expected '24800.9823269', error '0.0000000'
Test #88:
score: 0
Accepted
time: 33ms
memory: 140172kb
input:
188
output:
25065.94669159
result:
ok found '25065.9466916', expected '25065.9466916', error '0.0000000'
Test #89:
score: 0
Accepted
time: 31ms
memory: 142112kb
input:
189
output:
25332.31541441
result:
ok found '25332.3154144', expected '25332.3154144', error '0.0000000'
Test #90:
score: 0
Accepted
time: 19ms
memory: 144020kb
input:
190
output:
25600.08846737
result:
ok found '25600.0884674', expected '25600.0884674', error '0.0000000'
Test #91:
score: 0
Accepted
time: 27ms
memory: 146092kb
input:
191
output:
25869.26582267
result:
ok found '25869.2658227', expected '25869.2658227', error '0.0000000'
Test #92:
score: 0
Accepted
time: 16ms
memory: 148064kb
input:
192
output:
26139.84745272
result:
ok found '26139.8474527', expected '26139.8474527', error '0.0000000'
Test #93:
score: 0
Accepted
time: 31ms
memory: 150116kb
input:
193
output:
26411.83333013
result:
ok found '26411.8333301', expected '26411.8333301', error '0.0000000'
Test #94:
score: 0
Accepted
time: 32ms
memory: 152168kb
input:
194
output:
26685.22342772
result:
ok found '26685.2234277', expected '26685.2234277', error '0.0000000'
Test #95:
score: 0
Accepted
time: 19ms
memory: 154228kb
input:
195
output:
26960.01771852
result:
ok found '26960.0177185', expected '26960.0177185', error '0.0000000'
Test #96:
score: 0
Accepted
time: 19ms
memory: 156276kb
input:
196
output:
27236.21617575
result:
ok found '27236.2161757', expected '27236.2161758', error '0.0000000'
Test #97:
score: 0
Accepted
time: 20ms
memory: 158368kb
input:
197
output:
27513.81877284
result:
ok found '27513.8187728', expected '27513.8187728', error '0.0000000'
Test #98:
score: 0
Accepted
time: 42ms
memory: 160528kb
input:
198
output:
27792.82548338
result:
ok found '27792.8254834', expected '27792.8254834', error '0.0000000'
Test #99:
score: 0
Accepted
time: 23ms
memory: 162704kb
input:
199
output:
28073.23628120
result:
ok found '28073.2362812', expected '28073.2362812', error '0.0000000'
Test #100:
score: 0
Accepted
time: 36ms
memory: 164876kb
input:
200
output:
28355.05114027
result:
ok found '28355.0511403', expected '28355.0511403', error '0.0000000'