QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#105638#6395. Equation Discoveringwoyouxiangbaile#AC ✓430ms111132kbC++144.5kb2023-05-14 16:48:402023-05-14 16:48:45

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-14 16:48:45]
  • Judged
  • Verdict: AC
  • Time: 430ms
  • Memory: 111132kb
  • [2023-05-14 16:48:40]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i, d, u) for(int i = d; i <= u; ++i)
#define dep(i, u, d) for(int i = u; i >= d; --i)
#define cep(n) while(n--)
#define gep(i, a) for(int i = firs[a]; i; i = neig[i])
int ured() {
	int re = 0;
	char ch;
	do {
		ch = getchar();
	} while('9' < ch || ch < '0');
	do {
		re = re * 10 + (ch ^ '0');
	} while('0' <= (ch = getchar()) && ch <= '9');
	return re;
}
void uwit(int da) {
	int ch[21], cn = 0;
	do {
		ch[++cn] = da - da / 10 * 10;
	} while(da /= 10);
	do {
		putchar('0' ^ ch[cn]);
	} while(--cn);
}
const int _maxn = 20, _maxs = 5000011;
const long double _epsn = 0.00001, _epss = 0.00001;
int n;
long double x[_maxn], y[_maxn];
struct node {
	int cp;
	long double da[_maxn];
} atno, queu[_maxs], tono;
node operator+(node le, node ri) {
	node re;
	re . cp = le . cp + ri . cp + 2;
	rep(i, 0, n - 1) {
		re . da[i] = le . da[i] + ri . da[i];
	}
	return re;
}
node operator-(node le, node ri) {
	node re;
	re . cp = le . cp + ri . cp + 2;
	rep(i, 0, n - 1) {
		re . da[i] = le . da[i] - ri . da[i];
	}
	return re;
}
node operator*(node le, node ri) {
	node re;
	re . cp = le . cp + ri . cp + 2;
	rep(i, 0, n - 1) {
		re . da[i] = le . da[i] * ri . da[i];
	}
	return re;
}
node operator/(node le, node ri) {
	node re;
	re . cp = le . cp + ri . cp + 2;
	rep(i, 0, n - 1) {
		re . da[i] = le . da[i] / ri . da[i];
	}
	return re;
}
node qsin(node da) {
	node re;
	re . cp = da . cp + 1;
	rep(i, 0, n - 1) {
		re . da[i] = sin(da . da[i]);
	}
	return re;
}
node qcos(node da) {
	node re;
	re . cp = da . cp + 1;
	rep(i, 0, n - 1) {
		re . da[i] = cos(da . da[i]);
	}
	return re;
}
int head, tail, stat[_maxs], lson[_maxs], rson[_maxs];
bool operator<(node le, node ri) {
	if(le . cp != ri . cp) {
		return le . cp < ri . cp;
	}
	rep(i, 0, n - 1) {
		if(fabs(le . da[i] - ri . da[i]) > _epss) {
			return le . da[i] < ri . da[i];
		}
	}
	return 0;
}
set<node> sets;
bool pdif;
vector<int> dats[10];
void outp(int at) {
	putchar('(');
	if(stat[at] == 1) {
		outp(lson[at]), putchar('+'), outp(rson[at]);
	} else if(stat[at] == 2) {
		outp(lson[at]), putchar('-'), outp(rson[at]);
	} else if(stat[at] == 3) {
		outp(lson[at]), putchar('*'), outp(rson[at]);
	} else if(stat[at] == 4) {
		outp(lson[at]), putchar('/'), outp(rson[at]);
	} else if(stat[at] == 5) {
		putchar('s'), putchar('i'), putchar('n'), outp(lson[at]);
	} else if(stat[at] == 6) {
		putchar('c'), putchar('o'), putchar('s'), outp(lson[at]);
	} else {
		putchar('x');
	}
	putchar(')');
}
int main() {
	n = ured();
	rep(i, 0, n - 1) {
		scanf("%Lf%Lf", &x[i], &y[i]), queu[1] . da[i] = x[i];
	}
	sets . insert(queu[++tail]);
	while(head < tail) {
		pdif = 1, atno = queu[++head];
		rep(i, 0, n - 1) {
			if(fabs(atno . da[i] - y[i]) > _epsn) {
				pdif = 0;
				break;
			}
		}
		if(pdif) {
			outp(head), putchar('\n');
			break;
		}
		dats[atno . cp] . push_back(head);
		rep(i, 0, 7 - atno . cp) {
			for(int j : dats[i]) {
				if(!sets . count(tono = atno + queu[j])) {
					sets . insert(tono), queu[++tail] = tono, stat[tail] = 1, lson[tail] = head, rson[tail] = j;
				}
				if(!sets . count(tono = atno - queu[j])) {
					sets . insert(tono), queu[++tail] = tono, stat[tail] = 2, lson[tail] = head, rson[tail] = j;
				}
				if(!sets . count(tono = queu[j] - atno)) {
					sets . insert(tono), queu[++tail] = tono, stat[tail] = 2, lson[tail] = j, rson[tail] = head;
				}
				if(!sets . count(tono = atno * queu[j])) {
					sets . insert(tono), queu[++tail] = tono, stat[tail] = 3, lson[tail] = head, rson[tail] = j;
				}
				pdif = 1;
				rep(k, 0, n - 1) {
					if(fabs(queu[j] . da[k]) < 0.01) {
						pdif = 0;
						break;
					}
				}
				if(pdif && !sets . count(tono = atno / queu[j])) {
					sets . insert(tono), queu[++tail] = tono, stat[tail] = 4, lson[tail] = head, rson[tail] = j;
				}
				pdif = 1;
				rep(k, 0, n - 1) {
					if(fabs(atno . da[k]) < 0.01) {
						pdif = 0;
						break;
					}
				}
				if(pdif && !sets . count(tono = queu[j] / atno)) {
					sets . insert(tono), queu[++tail] = tono, stat[tail] = 4, lson[tail] = j, rson[tail] = head;
				}
			}
		}
		if(atno . cp <= 8 && !sets . count(tono = qsin(atno))) {
			sets . insert(tono), queu[++tail] = tono, stat[tail] = 5, lson[tail] = head;
		}
		if(atno . cp <= 8 && !sets . count(tono = qcos(atno))) {
			sets . insert(tono), queu[++tail] = tono, stat[tail] = 6, lson[tail] = head;
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5700kb

input:

3
1.000000 1.000000
2.000000 4.000000
3.000000 9.000000

output:

((x)*(x))

result:

ok great!!

Test #2:

score: 0
Accepted
time: 6ms
memory: 8668kb

input:

3
0.618000 1.517072
0.314000 3.132637
1.414000 0.494016

output:

((sin(x))/((x)*(x)))

result:

ok great!!

Test #3:

score: 0
Accepted
time: 2ms
memory: 5612kb

input:

5
77.685777 233.057331
-66.445083 -199.335249
79.966717 239.900151
84.982130 254.946390
-31.528900 -94.586700

output:

(((x)+(x))+(x))

result:

ok great!!

Test #4:

score: 0
Accepted
time: 6ms
memory: 9108kb

input:

5
25.032427 -0.100652
38.727324 1.658518
27.684334 -0.669555
64.282391 8.275303
52.640700 -0.962660

output:

((sin(x))/(cos(x)))

result:

ok great!!

Test #5:

score: 0
Accepted
time: 35ms
memory: 19160kb

input:

5
78.611917 -0.992212
-29.857271 1.011993
-75.513655 1.006611
68.512394 1.145128
7.961096 0.881661

output:

(((sin(x))*(sin(x)))+(cos(x)))

result:

ok great!!

Test #6:

score: 0
Accepted
time: 189ms
memory: 62860kb

input:

5
-78.733375 0.503570
-20.187183 0.735779
-38.984992 0.730890
47.859232 0.622831
-19.657164 0.641512

output:

(sin(sin(cos(cos(x)))))

result:

ok great!!

Test #7:

score: 0
Accepted
time: 6ms
memory: 6484kb

input:

5
3.241091 -32.628130
-83.514144 86.463432
33.586619 40.691607
41.123543 -147.352644
26.896326 27.404018

output:

((x)/(sin(x)))

result:

ok great!!

Test #8:

score: 0
Accepted
time: 383ms
memory: 94812kb

input:

20
-4.908422 -0.693287
3.569189 0.328182
1.946572 -0.667466
6.515336 -0.829948
-1.394076 0.752980
6.722989 0.831881
1.241795 0.835231
-2.443177 -0.143098
-4.180762 -0.803482
1.511247 0.589509
0.627755 0.554244
-1.865604 -0.470029
-4.756347 -0.656984
1.850611 -0.426016
6.580133 -0.474416
6.861815 -0....

output:

(sin(sin((x)/(sin((x)/((x)*(x)))))))

result:

ok great!!

Test #9:

score: 0
Accepted
time: 13ms
memory: 14180kb

input:

20
76.797930 0.000002
-76.263778 -0.000002
55.449039 0.000006
10.462093 0.000873
-78.051671 -0.000002
-52.781249 -0.000007
47.053973 0.000010
96.629212 0.000001
-40.697847 -0.000015
31.141805 0.000033
-87.087384 -0.000002
-54.709885 -0.000006
-65.741847 -0.000004
-87.430820 -0.000001
9.420126 0.0011...

output:

(((x)/(x))/(((x)*(x))*(x)))

result:

ok great!!

Test #10:

score: 0
Accepted
time: 5ms
memory: 6324kb

input:

20
24.490647 23.891773
17.327799 16.329001
21.204241 21.912414
83.489542 84.461510
-55.546573 -54.703972
-7.608368 -8.578356
-3.286697 -3.142101
-66.606831 -66.014954
-44.896454 -45.688502
97.541741 97.389961
-59.986043 -59.694554
57.723989 58.646803
-99.857351 -99.233536
29.134673 28.376609
-98.668...

output:

((sin(x))+(x))

result:

ok great!!

Test #11:

score: 0
Accepted
time: 2ms
memory: 6412kb

input:

20
89.594917 88.596688
-45.187625 -44.253669
97.451471 97.513530
35.078537 35.576300
82.504351 81.771201
-49.755211 -50.243625
-23.019693 -23.876242
-45.247155 -44.293590
75.324114 75.398156
78.533049 78.526282
99.112156 100.100628
31.983437 31.445903
71.251578 70.407388
-44.178279 -43.983549
-25.28...

output:

((x)-(sin(x)))

result:

ok great!!

Test #12:

score: 0
Accepted
time: 41ms
memory: 18924kb

input:

20
16.664144 7.850741
44.708237 22.196248
-10.852343 1.533223
-42.713221 -12.119419
-27.815914 -11.038511
31.908696 13.299065
-82.394044 40.761558
-37.317157 -12.907073
-35.369997 17.659068
93.569121 -45.722539
-30.589159 -15.242258
16.180069 6.553209
56.572831 1.366451
99.591187 -47.440823
12.73229...

output:

(((sin(x))*(x))*(cos(x)))

result:

ok great!!

Test #13:

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

input:

20
-583.519562 0.000000
-169.653469 0.000000
372.798856 0.000000
180.084282 0.000000
139.388742 0.000000
-648.300263 0.000000
-859.523046 0.000000
-267.278551 0.000000
635.554372 0.000000
299.925737 0.000000
-628.299469 0.000000
169.393099 0.000000
556.144161 0.000000
-881.876627 0.000000
328.692044...

output:

((x)-(x))

result:

ok great!!

Test #14:

score: 0
Accepted
time: 2ms
memory: 5712kb

input:

20
746.491049 746.491049
414.031997 414.031997
-975.051138 -975.051138
45.313068 45.313068
-181.090458 -181.090458
119.607074 119.607074
245.794647 245.794647
-794.156219 -794.156219
461.647608 461.647608
-392.604379 -392.604379
384.522118 384.522118
-461.749513 -461.749513
766.462890 766.462890
244...

output:

(x)

result:

ok great!!

Test #15:

score: 0
Accepted
time: 46ms
memory: 20960kb

input:

20
4.278335 0.092599
3.559350 0.559919
-2.517239 0.403581
-0.955317 0.182475
3.048015 0.888213
-0.638367 0.393205
-2.188885 0.183959
-0.367275 0.597938
1.106453 0.948186
0.339096 0.971773
-0.678258 0.364003
4.364111 0.060002
-0.671364 0.369012
-2.777257 0.600136
1.617698 0.909755
-3.400784 0.950952
...

output:

(sin((sin(x))+((x)/(x))))

result:

ok great!!

Test #16:

score: 0
Accepted
time: 215ms
memory: 66284kb

input:

20
3.692126 -0.260752
0.663419 1.200876
1.167172 0.874743
4.852602 0.631308
3.373109 -0.334749
4.749943 0.529545
-2.549440 -0.245748
-1.158832 0.881804
4.115764 -0.040747
-3.401216 -0.330886
-4.320685 0.119451
-0.070540 1.332133
-4.666465 0.446117
-4.720184 0.499803
-1.731319 0.332854
4.232513 0.046...

output:

((sin(sin(cos((x)/(x)))))+(sin(cos(x))))

result:

ok great!!

Test #17:

score: 0
Accepted
time: 349ms
memory: 94764kb

input:

20
1.462467 0.804429
-2.922001 0.192241
4.580542 -0.620639
-0.475001 -0.799291
-1.988595 -0.234001
1.262913 0.840075
-3.176510 -0.034797
2.030387 0.180297
-3.244547 -0.099928
-3.321420 -0.164361
-0.538138 -0.818609
2.485817 -0.209990
-0.282936 -0.652106
0.964792 0.840607
-1.300754 -0.837872
4.323400...

output:

(sin(sin((sin(sin((x)+(x))))+(sin(x)))))

result:

ok great!!

Test #18:

score: 0
Accepted
time: 183ms
memory: 54808kb

input:

20
-1.290592 0.818752
0.639318 0.516086
-4.576452 0.791075
2.349231 0.829843
3.053369 0.646833
-4.276424 0.836563
-4.295090 0.835111
1.704429 0.790551
1.694925 0.788364
0.763954 0.527671
-0.477936 0.769603
0.395468 0.525360
0.686854 0.519231
-1.940048 0.637497
2.188388 0.840879
1.028990 0.584344
3.9...

output:

(sin(cos(sin((cos((x)-(x)))+(x)))))

result:

ok great!!

Test #19:

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

input:

20
-0.425664 0.425664
5.789130 -5.789130
-3.787451 3.787451
0.301151 -0.301151
-8.592688 8.592688
2.669073 -2.669073
5.308311 -5.308311
-0.139985 0.139985
-5.857648 5.857648
-4.992568 4.992568
6.105319 -6.105319
-3.765244 3.765244
5.912188 -5.912188
-6.224392 6.224392
-0.543340 0.543340
3.434037 -3....

output:

((x)-((x)+(x)))

result:

ok great!!

Test #20:

score: 0
Accepted
time: 2ms
memory: 8732kb

input:

20
466.316736 -0.978078
-899.828376 0.971830
493.698428 0.451443
543.034476 -0.444891
547.435563 -0.716269
-477.216617 -0.300738
397.144177 -0.964489
-215.994986 0.699650
-125.191685 -0.454687
-278.649888 0.814495
958.350526 0.164022
-505.445050 0.344182
-930.587439 0.625688
397.543136 -0.991345
-25...

output:

(((x)-(x))-(sin(x)))

result:

ok great!!

Test #21:

score: 0
Accepted
time: 9ms
memory: 10900kb

input:

20
999.999999 0.987127
-999.999999 0.987127
100.000001 -0.333949
-100.000001 -0.333949
999.999998 -0.829877
-999.999998 -0.829877
512.000001 -0.871928
-512.000001 -0.871928
511.999999 -0.985382
-511.999999 -0.985382
0.000000 0.000000
0.000001 0.000000
-0.000001 0.000000
0.180000 0.001050
-0.180000 0...

output:

(sin(((x)*(x))*((x)*(x))))

result:

ok great!!

Test #22:

score: 0
Accepted
time: 182ms
memory: 55948kb

input:

20
0.009999 0.914653
0.009999 0.914653
0.009999 0.914653
0.009999 0.914653
0.009999 0.914653
0.009999 0.914653
0.009999 0.914653
1.000000 0.914653
1.000000 0.914653
2.005000 0.914653
2.005000 0.914653
3.000000 0.914653
3.000000 0.914653
0.009999 0.914653
0.009999 0.914653
0.009999 0.914653
0.009999 ...

output:

(cos(cos(((cos(x))+(cos(x)))/(cos(x)))))

result:

ok great!!

Test #23:

score: 0
Accepted
time: 19ms
memory: 11252kb

input:

1
31.424306 31.456129

output:

(((x)/((x)*(x)))+(x))

result:

ok great!!

Test #24:

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

input:

20
-29.440025 807.835022
19.414601 415.755934
11.492851 155.071326
18.966989 397.680650
3.027310 15.219226
-4.525550 11.429503
-7.906286 46.696786
-21.105731 403.240419
16.717653 312.915228
25.349563 693.299470
28.071737 844.165892
28.141608 848.233317
-26.371446 642.710272
-13.802857 162.913147
-23...

output:

(((x)*(x))+((x)+(x)))

result:

ok great!!

Test #25:

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

input:

20
458.594270 0.909297
236.772098 0.909297
679.844094 0.909297
-113.768271 0.909297
-919.765157 0.909297
450.713950 0.909297
-560.756795 0.909297
35.253093 0.909297
-530.329136 0.909297
-846.165765 0.909297
-294.618124 0.909297
595.795664 0.909297
441.685140 0.909297
220.854674 0.909297
-649.606144 ...

output:

(sin(((x)+(x))/(x)))

result:

ok great!!

Test #26:

score: 0
Accepted
time: 2ms
memory: 7696kb

input:

4
0.009999 1.000000
1.000000 1.000000
2.000000 1.000000
3.000000 1.000000

output:

(((x)+(x))/((x)+(x)))

result:

ok great!!

Test #27:

score: 0
Accepted
time: 40ms
memory: 27360kb

input:

4
1.560797 17.311340
1.000000 0.616661
2.000000 -0.369041
3.000000 -0.166678

output:

((cos(sin(x)))/((cos(x))*((x)+(x))))

result:

ok great!!

Test #28:

score: 0
Accepted
time: 370ms
memory: 109052kb

input:

4
0.020000 0.712709
1.000000 0.577284
2.000000 0.964383
3.000000 0.786224

output:

(cos(sin((cos(sin(cos((x)/(x)))))+(x))))

result:

ok great!!

Test #29:

score: 0
Accepted
time: 29ms
memory: 13520kb

input:

1
10.000000 9.990000

output:

((x)-(((x)/(x))/((x)*(x))))

result:

ok great!!

Test #30:

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

input:

2
0.026592 0.026593
4.000000 260.000000

output:

((((x)*(x))*((x)*(x)))+(x))

result:

ok great!!

Test #31:

score: 0
Accepted
time: 393ms
memory: 98256kb

input:

20
-816.944077 0.750063
364.252903 0.749797
377.702803 0.739860
-64.648254 0.723984
960.420578 0.734135
876.304536 0.749578
-718.016803 0.722938
-720.680010 0.725173
669.591341 0.746462
-835.716345 0.750360
611.456898 0.727346
-401.888640 0.749253
-59.913119 0.749372
-421.048989 0.750298
495.542911 ...

output:

(cos(cos(cos(cos(cos(cos(cos(cos(cos(x))))))))))

result:

ok great!!

Test #32:

score: 0
Accepted
time: 430ms
memory: 111132kb

input:

20
-966.243761 0.499984
-775.541582 -0.343886
665.144672 -0.467363
-440.569467 -0.446768
-15.642683 -0.064867
-891.727356 0.368493
-428.695562 -0.501273
-944.141182 -0.501731
265.202915 0.498506
-979.532068 0.423344
-678.301273 0.253567
125.728556 0.064444
-465.052762 -0.095704
-183.526425 -0.498649...

output:

(sin(sin(sin(sin(sin(sin(sin(sin(sin(x))))))))))

result:

ok great!!

Test #33:

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

input:

20
167.504612 669.176868
-132.494106 -530.496735
223.716049 894.248735
-14.542026 -59.087262
83.792869 336.028843
46.267758 185.826345
90.986202 364.064505
243.671799 973.706807
176.221425 705.173795
-140.883003 -564.001461
-25.914422 -104.362161
83.745358 335.862277
-92.043462 -367.367900
16.845939...

output:

((((x)+(x))+((x)+(x)))+(sin(x)))

result:

ok great!!

Test #34:

score: 0
Accepted
time: 8ms
memory: 12156kb

input:

20
5.820261 -23.727611
89.024912 -355.227137
78.465702 -313.788761
189.581597 -757.441601
-26.277637 104.199881
-58.876286 234.778122
180.037331 -720.972254
57.254054 -228.367888
-180.418016 722.647178
61.635602 -247.473082
126.339101 -504.731198
-192.871864 772.431509
-69.108582 276.440784
20.47183...

output:

((sin(x))-(((x)+(x))+((x)+(x))))

result:

ok great!!

Test #35:

score: 0
Accepted
time: 17ms
memory: 12344kb

input:

20
-4.724302 498.103725
-3.940617 172.814337
-2.254073 -20.019734
2.417435 22.626021
4.576524 -434.632501
-3.789730 124.524863
-0.923911 -0.581439
-2.730462 -22.213656
-1.227515 -2.137958
-2.004088 -14.640510
-1.374969 -3.505828
-4.749463 508.486587
-0.919612 -0.568834
-1.895851 -12.242133
2.276076 ...

output:

((((x)*(x))*((x)*(x)))*(sin(x)))

result:

ok great!!

Test #36:

score: 0
Accepted
time: 21ms
memory: 15428kb

input:

20
-1.862076 -0.079675
4.978934 -0.001570
-1.706248 -0.116906
3.159038 -0.000175
-2.164361 -0.037776
4.298608 -0.002682
3.437089 -0.002087
0.898312 1.201300
-0.915297 -1.129496
4.614390 -0.002195
0.547090 5.806825
-1.238625 -0.401631
-3.916926 0.002974
-0.651893 -3.359412
-0.913229 -1.137947
-3.8357...

output:

((sin(x))/(((x)*(x))*((x)*(x))))

result:

ok great!!

Test #37:

score: 0
Accepted
time: 16ms
memory: 9260kb

input:

20
999.999999 0.987127
-999.999999 0.987127
100.000001 -0.333949
-100.000001 -0.333949
999.999998 -0.829877
-999.999998 -0.829877
512.000001 -0.871928
-512.000001 -0.871928
511.999999 -0.985382
-511.999999 -0.985382
754.901184 0.143249
0.000001 0.000000
-0.000001 0.000000
0.180000 0.001050
-0.180000...

output:

(sin(((x)*(x))*((x)*(x))))

result:

ok great!!