QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#131713 | #4683. Qanat | PetroTarnavskyi# | AC ✓ | 152ms | 18468kb | C++17 | 1.8kb | 2023-07-27 22:12:38 | 2023-07-27 22:12:40 |
Judging History
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