QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#153016#6829. It Takes Two of Twoqzez#AC ✓42ms164876kbC++141.7kb2023-08-29 08:47:212023-08-29 08:47:22

Judging History

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

  • [2023-08-29 08:47:22]
  • 评测
  • 测评结果:AC
  • 用时:42ms
  • 内存:164876kb
  • [2023-08-29 08:47:21]
  • 提交

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,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

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'