QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#131713#4683. QanatPetroTarnavskyi#AC ✓152ms18468kbC++171.8kb2023-07-27 22:12:382023-07-27 22:12:40

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-27 22:12:40]
  • 评测
  • 测评结果:AC
  • 用时:152ms
  • 内存:18468kb
  • [2023-07-27 22:12:38]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

typedef __float128 db;

db ta;
db solve(db x){
	//from x to 1
	db M = (ta + 1) * (1 - x) / 2;
	
	//cout << x << " " << 1 << endl;
	//cout << M << endl;
	
	db h = x * ta;	
	db res = h * h / 2;
	
	//from 0 to M y + h
	res += M * M / 2 + h * M;
	//from 0 to 1 - x - M y + 1
	res += (1 - x - M) * (1 - x - M)/2 + (1 - x - M) * ta;
	
	return res;
}



const int N = 1 << 17;
db res[N];
vector<db> ans[N]; 



int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int w, h, n;
	cin >> w >> h >> n;
	ta = 1.0 * h / w;
	
	
	//cout << solve(3./8.) << endl;
	//return 0;
	res[0] = solve(0);
	
	//cout << 8 * 8 *(solve(3./8.) + res[0] * 3/8 * 3/8 + 1./8) << endl;
	//cout << res[0] << endl;
	//return 0;
	FOR(i, 1, n + 1){
		db l = 0, r = 1;
		FOR(t, 0, 200){
			db m1 = (2 * l + r) / 3;
			db m2 = (l + 2 * r) / 3;
			
			db res1 = res[i - 1] * (m1 * m1) + solve(m1);
			db res2 = res[i - 1] * (m2 * m2) + solve(m2);
			
			if(res1 > res2)
				l = m1;
			else
				r = m2;
		}
		res[i] = res[i - 1] * (l * l) + solve(l);
		for(auto x : ans[i - 1])
			ans[i].PB(x * l);
		ans[i].PB(l);
	}
	res[n] += ta * ta / 2;
	//cout << res[n] << endl;
	cout << fixed << setprecision(10);
	
	cout << (long double)(1.0 * res[n] * w * w) << "\n";
	FOR(i, 0, min(n, 10))
		cout << (long double)(ans[n][i] * w) << "\n";
	
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

8 4 1

output:

31.5000000000
3.0000000000

result:

ok 2 numbers

Test #2:

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

input:

195 65 2

output:

12220.0000000000
48.0000000000
108.0000000000

result:

ok 3 numbers

Test #3:

score: 0
Accepted
time: 152ms
memory: 18468kb

input:

10000 1 1000

output:

30141.8856771285
9.9567212031
19.9134426053
29.8701644058
39.8268868037
49.7836099982
59.7403341883
69.6970595732
79.6537863521
89.6105147240
99.5672448881

result:

ok 11 numbers

Test #4:

score: 0
Accepted
time: 3ms
memory: 8784kb

input:

2 1 5

output:

1.9115325553
0.0298525799
0.0796068796
0.1824324324
0.4068796069
0.9025798526

result:

ok 6 numbers

Test #5:

score: 0
Accepted
time: 3ms
memory: 8600kb

input:

10000 9999 1

output:

99989999.7500499998
0.9999500000

result:

ok 2 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 7700kb

input:

10000 1 1

output:

12505000.4999999988
4999.9999500000

result:

ok 2 numbers

Test #7:

score: 0
Accepted
time: 78ms
memory: 9352kb

input:

10000 51 500

output:

436223.5625306686
3.8915076140
7.7832176694
11.6753326184
15.5680549340
19.4615871209
23.3561317258
27.2518913484
31.1490686512
35.0478663707
38.9484873276

result:

ok 11 numbers

Test #8:

score: 0
Accepted
time: 73ms
memory: 10436kb

input:

10000 185 500

output:

1587574.0560213342
0.0010603304
0.0021213869
0.0031838960
0.0042485852
0.0053161835
0.0063874220
0.0074630343
0.0085437567
0.0096303293
0.0107234961

result:

ok 11 numbers

Test #9:

score: 0
Accepted
time: 0ms
memory: 6936kb

input:

1000 995 2

output:

994993.8121124806
0.0248757750
4.9876240679

result:

ok 3 numbers

Test #10:

score: 0
Accepted
time: 0ms
memory: 7904kb

input:

10000 1 9

output:

2505001.8999997806
999.9996700001
1999.9993600001
2999.9990900002
3999.9988800002
4999.9987500002
5999.9987200002
6999.9988100002
7999.9990400002
8999.9994300001

result:

ok 10 numbers

Test #11:

score: 0
Accepted
time: 4ms
memory: 8496kb

input:

10000 1 10

output:

2277729.3409087982
909.0905454546
1818.1811090911
2727.2717090912
3636.3623636367
4545.4530909095
5454.5439090913
6363.6348363640
7272.7258909094
8181.8170909093
9090.9084545456

result:

ok 11 numbers

Test #12:

score: 0
Accepted
time: 3ms
memory: 8028kb

input:

10000 1 11

output:

2088335.5694440638
833.3329361112
1666.6658888891
2499.9988750004
3333.3319111116
4166.6650138894
4999.9982000005
5833.3314861116
6666.6648888894
7499.9984250004
8333.3321111114

result:

ok 11 numbers

Test #13:

score: 0
Accepted
time: 124ms
memory: 16696kb

input:

5374 23 881

output:

105634.9724814953
0.3124779220
0.6249672917
0.9374795572
1.2500261674
1.5626185726
1.8752682245
2.1879865773
2.5007850873
2.8136752140
3.1266684203

result:

ok 11 numbers

Test #14:

score: 0
Accepted
time: 14ms
memory: 7744kb

input:

7868 6 86

output:

202023.7744142247
90.3042458267
180.6085966832
270.9131575993
361.2180336049
451.5233297307
541.8291510076
632.1356024671
722.4427891414
812.7508160638
903.0597882684

result:

ok 11 numbers

Test #15:

score: 0
Accepted
time: 91ms
memory: 11776kb

input:

458 4 583

output:

1567.6981632763
0.0083352389
0.0166717495
0.0250108035
0.0333536733
0.0417016317
0.0500559523
0.0584179096
0.0667887794
0.0751698387
0.0835623662

result:

ok 11 numbers

Test #16:

score: 0
Accepted
time: 122ms
memory: 15020kb

input:

948 7 778

output:

5676.3987227717
0.0058039041
0.0116084411
0.0174142441
0.0232219461
0.0290321805
0.0348455809
0.0406627813
0.0464844160
0.0523111200
0.0581435286

result:

ok 11 numbers

Test #17:

score: 0
Accepted
time: 50ms
memory: 9116kb

input:

5964 32 326

output:

164105.0394318787
7.6231647479
15.2467684332
22.8712500183
30.4970485164
38.1246030165
45.7543527087
53.3867369093
61.0221950865
68.6611668855
76.3040921538

result:

ok 11 numbers

Test #18:

score: 0
Accepted
time: 18ms
memory: 7448kb

input:

9810 46 137

output:

446648.1376693290
62.0557339887
124.1141969496
186.1781179749
248.2502263968
310.3332519076
372.4299246796
434.5429754855
496.6751358179
558.8291380099
621.0077153553

result:

ok 11 numbers

Test #19:

score: 0
Accepted
time: 128ms
memory: 15600kb

input:

5506 26 889

output:

122360.7033236695
0.1928750622
0.3857587263
0.5786595944
0.7715862694
0.9645473555
1.1575514584
1.3506071856
1.5437231469
1.7369079551
1.9301702255

result:

ok 11 numbers

Test #20:

score: 0
Accepted
time: 52ms
memory: 9488kb

input:

2274 11 359

output:

21510.3112681916
2.6701863905
5.3404977453
8.0110590347
10.6819952406
13.3534313625
16.0254924231
18.6983034747
21.3719896043
24.0466759402
26.7224876573

result:

ok 11 numbers

Test #21:

score: 0
Accepted
time: 84ms
memory: 11220kb

input:

709 3 571

output:

1819.3566623194
0.2770796887
0.5541692993
0.8312787539
1.1084179755
1.3855968881
1.6628254169
1.9401134893
2.2174710345
2.4949079843
2.7724342734

result:

ok 11 numbers

Test #22:

score: 0
Accepted
time: 20ms
memory: 8496kb

input:

8601 87 124

output:

655817.0854604141
42.3466997734
84.7020658646
127.0747663650
169.4734729136
211.9068624715
254.3836190978
296.9124357265
339.5020159460
382.1610757800
424.8983454714

result:

ok 11 numbers

Test #23:

score: 0
Accepted
time: 92ms
memory: 12044kb

input:

3207 2 638

output:

7649.0496519071
4.7626359598
9.5252756242
14.2879226977
19.0505808850
23.8132538907
28.5759454194
33.3386591756
38.1013988642
42.8641681897
47.6269708567

result:

ok 11 numbers

Test #24:

score: 0
Accepted
time: 3ms
memory: 8844kb

input:

2971 24 28

output:

114650.0147448116
100.5999723480
201.2130749576
301.8524398040
402.5312022905
503.2625029621
604.0594892214
704.9353170440
805.9031526962
906.9761744528
1008.1675743176

result:

ok 11 numbers

Test #25:

score: 0
Accepted
time: 132ms
memory: 16284kb

input:

8420 73 940

output:

525973.2933869036
0.0020138189
0.0040279405
0.0060426677
0.0080583034
0.0100751505
0.0120935125
0.0141136925
0.0161359945
0.0181607225
0.0201881808

result:

ok 11 numbers

Test #26:

score: 0
Accepted
time: 140ms
memory: 16504kb

input:

6704 50 943

output:

286734.4489952758
0.0067022043
0.0134051542
0.0201095955
0.0268162742
0.0335259364
0.0402393285
0.0469571976
0.0536802909
0.0604093565
0.0671451431

result:

ok 11 numbers

Test #27:

score: 0
Accepted
time: 147ms
memory: 17056kb

input:

4495 24 999

output:

92225.0890193178
0.0356803339
0.0713627022
0.1070491393
0.1427416802
0.1784423597
0.2141532135
0.2498762777
0.2856135892
0.3213671855
0.3571391052

result:

ok 11 numbers

Test #28:

score: 0
Accepted
time: 125ms
memory: 14976kb

input:

9270 32 846

output:

253507.4992270018
1.4488448025
2.8977241351
4.3466725286
5.7957245157
7.2449146312
8.6942774137
10.1438474053
11.5936591536
13.0437472117
14.4941461391

result:

ok 11 numbers

Test #29:

score: 0
Accepted
time: 119ms
memory: 13820kb

input:

9865 74 778

output:

624467.9141697422
0.0539172778
0.1078406238
0.1617761066
0.2157297963
0.2697077653
0.3237160883
0.3777608437
0.4318481140
0.4859839864
0.5401745535

result:

ok 11 numbers

Test #30:

score: 0
Accepted
time: 103ms
memory: 14940kb

input:

6422 52 782

output:

285713.1020584748
0.0187706693
0.0375438002
0.0563218544
0.0751072945
0.0939025840
0.1127101875
0.1315325714
0.1503722042
0.1692315562
0.1881131008

result:

ok 11 numbers

Test #31:

score: 0
Accepted
time: 74ms
memory: 9784kb

input:

3730 1 509

output:

8770.0875701663
7.2683472839
14.5366956127
21.8050460311
29.0733995840
36.3417573163
43.6101202728
50.8784894983
58.1468660376
65.4152509357
72.6836452372

result:

ok 11 numbers

Test #32:

score: 0
Accepted
time: 117ms
memory: 12988kb

input:

7689 70 720

output:

460629.1017366046
0.0184105648
0.0368241816
0.0552439030
0.0736727826
0.0921138753
0.1105702384
0.1290449313
0.1475410168
0.1660615612
0.1846096346

result:

ok 11 numbers

Test #33:

score: 0
Accepted
time: 147ms
memory: 15596kb

input:

8374 17 923

output:

122084.5082741225
3.4045691627
6.8091663878
10.2138197382
13.6185572768
17.0234070676
20.4283971755
23.8335556662
27.2389106071
30.6444900673
34.0503221174

result:

ok 11 numbers

Test #34:

score: 0
Accepted
time: 143ms
memory: 17388kb

input:

4417 22 938

output:

83064.1076870340
0.0834537546
0.1669116500
0.2503778270
0.3338564270
0.4173515920
0.5008674648
0.5844081892
0.6679779102
0.7515807744
0.8352209298

result:

ok 11 numbers

Test #35:

score: 0
Accepted
time: 100ms
memory: 13368kb

input:

7222 30 710

output:

185191.6362977215
1.3025078303
2.6050606122
3.9077032989
5.2104808466
6.5134382164
7.8166203753
9.1200722983
10.4238389695
11.7279653840
13.0324965493

result:

ok 11 numbers

Test #36:

score: 0
Accepted
time: 101ms
memory: 14316kb

input:

3810 19 746

output:

61880.1797734795
0.2769070057
0.5538277846
0.8307761103
1.1077657581
1.3848105052
1.6619241316
1.9391204206
2.2164131597
2.4938161412
2.7713431630

result:

ok 11 numbers

Test #37:

score: 0
Accepted
time: 82ms
memory: 10420kb

input:

5093 28 582

output:

121927.4003802696
0.8514558173
1.7029631069
2.5545733443
3.4063380112
4.2583085986
5.1105366099
5.9630735643
6.8159709993
7.6692804745
8.5230535743

result:

ok 11 numbers

Test #38:

score: 0
Accepted
time: 97ms
memory: 14108kb

input:

6834 19 711

output:

111261.7999465905
3.2818569446
6.5637646245
9.8457737758
13.1279351362
16.4102994456
19.6929174472
22.9758398880
26.2591175199
29.5428011001
32.8269413922

result:

ok 11 numbers

Test #39:

score: 0
Accepted
time: 114ms
memory: 14408kb

input:

9808 44 779

output:

368851.2586585200
0.8827973246
1.7656301831
2.6485341111
3.5315446469
4.4146973330
5.2980277177
6.1815713566
7.0653638135
7.9494406627
8.8338374897

result:

ok 11 numbers