QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#231735#6423. Fireworksveg#TL 8ms3900kbC++142.0kb2023-10-29 16:00:582023-10-29 16:00:59

Judging History

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

  • [2023-10-29 16:00:59]
  • 评测
  • 测评结果:TL
  • 用时:8ms
  • 内存:3900kb
  • [2023-10-29 16:00:58]
  • 提交

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...

result: