QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#231726#6423. Fireworksveg#TL 148ms3940kbC++142.0kb2023-10-29 15:58:022023-10-29 15:58:03

Judging History

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

  • [2023-10-29 15:58:03]
  • 评测
  • 测评结果:TL
  • 用时:148ms
  • 内存:3940kb
  • [2023-10-29 15:58:02]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define double long double
double n, m, p, tmp, ans, k, ww;
double down=0.999;
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 = 1949;
	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 <= 10; ++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: 148ms
memory: 3940kb

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: -100
Time Limit Exceeded

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:


result: