QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#231735 | #6423. Fireworks | veg# | TL | 8ms | 3900kb | C++14 | 2.0kb | 2023-10-29 16:00:58 | 2023-10-29 16:00:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define double long double
double n, m, p, tmp, ans, k, ww;
double down=0.95;
double calc(int k) {
return (k * n + m) / (1 - pow(1 - p, k));
}
double log_get(double mid) {
// return pow(1 - p, mid) * (-tmp * n * mid - m * tmp + n);
return mid + log(-tmp * n * mid - m * tmp + n) / log(tmp);
}
void div1(double l, double r) {
while (r - l > 1e-3) {
double mid = (l + r) / 2;
if (log_get(mid) < log(n) / log(tmp)) l = mid;
else r = mid;
}
int k1 = floor(l), k2 = ceil(l);
ans = min(ans, calc(k1));
ans = min(ans, calc(k2));
}
void div2(double l, double r) {
while (r - l > 1e-3) {
double mid = (l + r) / 2;
if (log_get(mid) < log(n) / log(tmp)) r = mid;
else l = mid;
}
int k1 = floor(l), k2 = ceil(l);
ans = min(ans, calc(k1));
ans = min(ans, calc(k2));
}
void SA() {
double t = 100;
while (t > 1e-6) {
double u = max((double)1, k + 1.0 * (rand() * 2 - RAND_MAX) / RAND_MAX*100000*t);
double w = calc((int)u);
double dt = ans - w;
if (dt > 0 || exp(dt / t) * RAND_MAX>rand()) k = u, ww = w;
if (w < ans) ans = w;
t*=down;
}
}
int main() {
int T;
cin >> T;
while (T--) {
scanf("%Lf%Lf%Lf", &n, &m, &p);
p /= 10000;
tmp = log(1 - p);
/*double l = 0, r = 1e9;
while (r - l > 1e-3) {
double lmid = l + (r - l) / 3;
double rmid = r - (r - l) / 3;
double lv = log_get(lmid);
double rv = log_get(rmid);
if (fabs(lv - rv) < 1e-4) {
l = lmid;
r = rmid;
} else if (lv < rv)
l = lmid;
else
r = rmid;
}
// cerr << l << endl;
ans = calc(1);
if (log_get(0) < log(n) / log(tmp) && log(n) / log(tmp) < log_get(l)) div1(0, l);
if (log_get(1e4) < log(n) / log(tmp) && log(n) / log(tmp) < log_get(l)) div2(l, 1e4);
// for (int i = 1; i <= 100; ++i) cerr << calc(i) << endl;
printf("%.6Lf\n", ans);*/
ans = ww = calc(1);
k = 50;
for (int i = 1; i <= 3; ++i) SA();
printf("%.6Lf\n", ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3768kb
input:
3 1 1 5000 1 1 1 1 2 10000
output:
4.000000 10141.585289 3.000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 6ms
memory: 3712kb
input:
20 10 27 2855 79 59 6888 65 72 7725 78 50 2888 31 21 5759 41 58 6619 47 27 3881 35 55 5095 77 7 6028 17 89 1792 84 60 8604 58 44 4923 88 27 3824 54 63 1482 19 42 5366 93 76 97 100 99 8660 96 36 4343 90 56 9515 24 44 9922
output:
89.729806 200.348432 177.346278 416.839878 90.293454 149.569421 190.672507 164.601521 139.349701 275.133110 167.364017 207.190737 300.732218 589.058849 101.877028 10796.887267 229.792148 303.937370 153.441934 68.534570
result:
ok 20 numbers
Test #3:
score: 0
Accepted
time: 3ms
memory: 3632kb
input:
10 954269343 987322500 9806 916720797 981711601 9728 902477101 957414437 9250 967013471 988735825 9674 985383693 926528961 9411 970653208 917703218 9331 998423148 911924940 9283 986159007 902133513 9759 953796828 947934512 9959 995334734 931874197 9944
output:
1980003919.029166 1951513567.023026 2010693554.594595 2021655257.390945 2031572260.121135 2023744964.098167 2057899480.771302 1934924193.052567 1909560538.206647 1938062078.640386
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 3ms
memory: 3652kb
input:
10 933722894 72 9673 975866948 5 9424 910984544 95 9682 994597175 6 9351 972675086 51 9712 952759975 51 9114 956482031 85 9478 921988922 72 9017 950640658 36 9893 965297247 78 9342
output:
965287879.665047 1035512471.349745 940905431.728982 1063626543.685167 1001518880.766063 1045380761.465877 1009160282.760076 1022500825.108129 960922565.450318 1033287652.536930
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 3ms
memory: 3660kb
input:
10 910088095 81 316 970640211 35 537 908853334 41 89 932269507 8 457 953224740 22 113 959834859 69 34 924852390 63 115 952730384 97 382 917634328 91 20 937287266 32 654
output:
28800258734.177215 18075237355.679702 102118356741.573034 20399770568.927790 84356173628.318584 282304390588.235294 80421952434.782609 24940588507.853403 458817209500.000000 14331610061.162080
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 4ms
memory: 3716kb
input:
10 968675373 962412132 104 923494255 934310785 381 922721350 957856460 282 978335370 917228676 825 951116860 942542480 359 999013758 972493824 676 930242700 964474169 342 968944030 984608304 520 965837594 909045242 369 990484700 925952624 479
output:
106669104052.294286 31076848077.761112 40771434362.895146 16579259543.363533 33660076568.701947 20209258011.501921 34581380127.395108 24798113234.332960 33145494087.728287 26925682159.120106
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 4ms
memory: 3664kb
input:
10 22 972733171 975 22 973609752 512 55 987399854 126 49 967364929 642 23 948126474 513 25 962813818 421 93 933323422 113 58 950364131 647 82 991906690 682 31 957667404 402
output:
972736672.681293 973616306.986936 987457697.396779 967376069.315485 948133283.101614 962822722.647579 933426898.317728 950377057.363343 991923706.585392 957678776.965345
result:
ok 10 numbers
Test #8:
score: 0
Accepted
time: 4ms
memory: 3900kb
input:
10 47 972371220 9743 65 949941115 9400 86 921812690 9736 11 927065494 9182 71 923766617 9378 63 941828720 9029 96 917539847 9084 88 952051332 9499 91 958386812 9427 64 950375055 9887
output:
972371465.901790 949941549.320473 921813131.821226 927065583.858390 923767096.493966 941829231.442623 917540568.647066 952051875.055215 958387391.921014 950375326.495619
result:
ok 10 numbers
Test #9:
score: 0
Accepted
time: 3ms
memory: 3628kb
input:
10 98 46 9403 99 89 9661 80 62 9450 25 20 9283 68 74 9328 54 14 9286 4 80 9574 35 61 9420 77 47 9943 22 9 9358
output:
153.142614 194.596833 150.264550 48.475708 152.229846 73.228516 87.737623 101.910828 124.710852 33.126736
result:
ok 10 numbers
Test #10:
score: 0
Accepted
time: 4ms
memory: 3776kb
input:
10 89 77 65 53 41 913 47 67 488 89 13 267 20 60 427 58 72 690 23 60 677 43 38 775 52 68 343 83 61 805
output:
15149.283838 795.195960 1340.262610 3590.647505 734.463108 1204.044042 568.432537 761.453450 1986.669558 1378.158448
result:
ok 10 numbers
Test #11:
score: 0
Accepted
time: 8ms
memory: 3720kb
input:
20 5 1000000000 4 3 999999979 5 5 1000000000 2 2 999999999 4 3 999999983 1 3 999999984 1 3 999999987 3 3 999999974 1 2 999999998 1 1 999999981 2 4 999999971 4 3 999999992 1 5 999999973 4 4 999999984 4 3 999999972 4 2 999999994 4 2 999999980 5 4 999999970 5 2 999999980 2 4 999999983 4
output:
1000153595.966846 1000078103.937719 1000289896.621388 1000066017.486278 1000342407.043464 1000342408.043494 1000125100.235102 1000342398.043195 1000236387.472665 1000066005.589948 1000125078.477629 1000342416.043734 1000153568.966509 1000125091.477759 1000095959.573884 1000066012.486253 1000053684.6...
result:
ok 20 numbers
Test #12:
score: -100
Time Limit Exceeded
input:
10000 15 999999991 6 16 999999975 2 12 999999978 9 7 999999993 4 19 999999980 5 20 999999977 5 13 999999995 10 11 999999979 6 19 999999995 5 6 999999982 10 15 999999978 1 2 999999974 5 12 999999980 4 18 999999997 1 12 999999992 10 20 999999970 6 2 999999999 2 13 999999984 1 16 999999984 2 16 9999999...
output:
1000289834.627434 1000834644.980374 1000162916.054420 1000209141.238760 1000424660.557302 1000444958.758944 1000159181.222367 1000218214.149088 1000424675.557871 1000078088.897095 1001470863.708315 1000053678.649081 1000342357.171558 1001732290.589738 1000147893.025167 1000376844.543859 1000125117.9...