QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#135673#6395. Equation DiscoveringUrgantTeamWA 1220ms128964kbC++237.4kb2023-08-05 21:23:322023-08-05 21:23:34

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-05 21:23:34]
  • 评测
  • 测评结果:WA
  • 用时:1220ms
  • 内存:128964kb
  • [2023-08-05 21:23:32]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long double ld;
typedef long long ll;

const ld EPS = 0.005;
const ld EPS_RES = 1e-4;

struct Node
{
 	int opcode;
 	int son[2];
};

ld valx[25], valy[25];
ld result[25][1005];

vector <vector <Node> > generate_expr(int deep, int state)
{
	if (state == 0)
	{
	 	return generate_expr(deep, 1);
 	}
 	if (state == 1)
 	{
 		vector <vector <Node> > A = generate_expr(deep, 2);

 		for (int lef = 0; lef <= deep - 2; lef++)
 		{
 			int rig = deep - 2 - lef;

 			vector <vector <Node> > B = generate_expr(lef, 1);
 			vector <vector <Node> > C = generate_expr(rig, 2);
 			for (const auto &x : B)
 				for (const auto &y : C)
 				{
 				 	vector <Node> D = x;
 				 	for (const auto &z : y) D.pb(z);
 				 	
 				 	Node new_node;
 				 	new_node.opcode = 2;
 				 	new_node.son[0] = (int) y.size() + 1;
 				 	new_node.son[1] = 1;
 				 	D.pb(new_node);

 				 	vector <Node> E = x;
 				 	for (const auto &z : y) E.pb(z);
 				 	
 				 	new_node.opcode = 3;
 				 	new_node.son[0] = (int) y.size() + 1;
 				 	new_node.son[1] = 1;
 				 	E.pb(new_node);

 				 	A.pb(D), A.pb(E);
 				}
 		}
 		return A;
 	}
 	if (state == 2)
 	{
 		vector <vector <Node> > A = generate_expr(deep, 3);

 		for (int lef = 0; lef <= deep - 2; lef++)
 		{
 			int rig = deep - 2 - lef;

 			{
    			vector <vector <Node> > B = generate_expr(lef, 0);
    			vector <vector <Node> > C = generate_expr(rig, 0);
    			for (const auto &x : B)
    				for (const auto &y : C)
    				{
    				 	vector <Node> D = x;
    				 	for (const auto &z : y) D.pb(z);
    				 	
    				 	Node new_node;
    				 	new_node.opcode = 4;
    				 	new_node.son[0] = (int) y.size() + 1;
    				 	new_node.son[1] = 1;
    				 	D.pb(new_node);

    				 	vector <Node> E = x;
    				 	for (const auto &z : y) E.pb(z);
    				 	
    				 	new_node.opcode = 5;
    				 	new_node.son[0] = (int) y.size() + 1;
    				 	new_node.son[1] = 1;
    				 	E.pb(new_node);

    				 	A.pb(D), A.pb(E);
    				}
    		}
 		}
 		return A;
 	}
 	if (state == 3)
 	{
 		if (deep == 0)
 		{
 		 	Node new_node;
 		 	new_node.opcode = 6;
 		 	return {{new_node}};
 		}

 		vector <vector <Node> > A = generate_expr(deep - 1, 0);

 		vector <vector <Node> > res;
 		for (const auto &x : A)
 		{
 			vector <Node> B = x, C = x;
 		
 			Node new_node;
 			new_node.opcode = 0;
 			new_node.son[0] = 1;
 			B.pb(new_node);

 			new_node.opcode = 1;
 			new_node.son[0] = 1;
 			C.pb(new_node);

 			res.pb(B), res.pb(C);
 		}
 		return res;
 	}
 	if (state == 4)
 	{
 		vector <vector <Node> > A;
 		for (int lef = 0; lef <= deep - 2; lef++)
 		{
 			int rig = deep - 2 - lef;

 			vector <vector <Node> > B = generate_expr(lef, 1);
 			vector <vector <Node> > C = generate_expr(rig, 2);
 			for (const auto &x : B)
 				for (const auto &y : C)
 				{
 				 	vector <Node> D = x;
 				 	for (const auto &z : y) D.pb(z);
 				 	
 				 	Node new_node;
 				 	new_node.opcode = 2;
 				 	new_node.son[0] = (int) y.size() + 1;
 				 	new_node.son[1] = 1;
 				 	D.pb(new_node);

 				 	vector <Node> E = x;
 				 	for (const auto &z : y) E.pb(z);
 				 	
 				 	new_node.opcode = 3;
 				 	new_node.son[0] = (int) y.size() + 1;
 				 	new_node.son[1] = 1;
 				 	E.pb(new_node);

 				 	A.pb(D), A.pb(E);
 				}
 		}
 		return A; 	
 	}
 	return {};
}

string recover_answer(vector <Node> tree)
{
 	Node last = tree.back();
 	string ans;
 	if (last.opcode == 0)
 	{
 		string L = recover_answer(vector <Node>(tree.begin(), tree.begin() + (int) tree.size() - 1));
 		ans = "sin(" + L + ")";
 	}
 	if (last.opcode == 1)
 	{
 		string L = recover_answer(vector <Node>(tree.begin(), tree.begin() + (int) tree.size() - 1));
 		ans = "cos(" + L + ")";
 	}
 	if (last.opcode == 2)
 	{
 		int lef = last.son[0];

 		string L = recover_answer(vector <Node>(tree.begin(), tree.begin() + (int) tree.size() - lef));
 		string R = recover_answer(vector <Node>(tree.begin() + (int) tree.size() - lef, tree.begin() + (int) tree.size() - 1));
 		ans = L + "+" + R;
 	}
 	if (last.opcode == 3)
 	{
 		int lef = last.son[0];

 		string L = recover_answer(vector <Node>(tree.begin(), tree.begin() + (int) tree.size() - lef));
 		string R = recover_answer(vector <Node>(tree.begin() + (int) tree.size() - lef, tree.begin() + (int) tree.size() - 1));
 		ans = L + "-" + R;
 	}
 	if (last.opcode == 4)
 	{
 		int lef = last.son[0];

 		string L = recover_answer(vector <Node>(tree.begin(), tree.begin() + (int) tree.size() - lef));
 		string R = recover_answer(vector <Node>(tree.begin() + (int) tree.size() - lef, tree.begin() + (int) tree.size() - 1));
 		ans = "(" + L + ")/(" + R + ")";
 	}
 	if (last.opcode == 5)
 	{
 		int lef = last.son[0];

 		string L = recover_answer(vector <Node>(tree.begin(), tree.begin() + (int) tree.size() - lef));
 		string R = recover_answer(vector <Node>(tree.begin() + (int) tree.size() - lef, tree.begin() + (int) tree.size() - 1));
 		ans = "(" + L + ")*(" + R + ")";
 	}
 	if (last.opcode == 6)
 	{
 		ans = "x";
 	}
 	return ans;
}

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> valx[i] >> valy[i];

	vector <vector <Node> > all_var;
	for (int i = 0; i <= 9; i++)
	{
	 	vector <vector <Node> > res = generate_expr(i, 0);
	 	for (const auto &x : res) all_var.pb(x);
	}

	for (const auto &tree : all_var)
	{
	 	bool FLAG = true;
	 	for (int num = 0; num < (int) tree.size(); num++)
	 	{
	 	 	const Node &node = tree[num];
	 	 	if (node.opcode == 0)
	 	 	{
	 	 	 	int pr = num - node.son[0];
	 	 	 	for (int i = 1; i <= n; i++) result[i][num] = sin(result[i][pr]);
	 	 	}
	 	 	if (node.opcode == 1)
	 	 	{
	 	 		int pr = num - node.son[0];
	 	 	 	for (int i = 1; i <= n; i++) result[i][num] = cos(result[i][pr]);
	 	 	}
	 	 	if (node.opcode == 2)
	 	 	{
	 	 		int lef = num - node.son[0];
	 	 		int rig = num - node.son[1];
	 	 		for (int i = 1; i <= n; i++) result[i][num] = result[i][lef] + result[i][rig];
	 	 	}
	 	 	if (node.opcode == 3)
	 	 	{
	 	 		int lef = num - node.son[0];
	 	 		int rig = num - node.son[1];
	 	 		for (int i = 1; i <= n; i++) result[i][num] = result[i][lef] - result[i][rig];
	 	 	}
	 	 	if (node.opcode == 4)
	 	 	{
	 	 		int lef = num - node.son[0];
	 	 		int rig = num - node.son[1];
	 	 		for (int i = 1; i <= n; i++)
	 	 		{
	 	 			if (fabs(result[i][rig]) < EPS) {FLAG = false; continue;}
	 	 			result[i][num] = result[i][lef] / result[i][rig];
	 	 		}
	 	 	}
	 	 	if (node.opcode == 5)
	 	 	{
	 	 		int lef = num - node.son[0];
	 	 		int rig = num - node.son[1];
	 	 		for (int i = 1; i <= n; i++) result[i][num] = result[i][lef] * result[i][rig];
	 	 	}
	 	 	if (node.opcode == 6)
	 	 	{
	 	 	 	for (int i = 1; i <= n; i++) result[i][num] = valx[i];
	 	 	}
	 	}
	 	//cout << recover_answer(tree) << '\n';
	 	if (!FLAG) continue;

	 	bool ANS = true;
	 	for (int i = 1; i <= n; i++)
	 		if (fabs(valy[i] - result[i][(int) tree.size() - 1]) > EPS_RES) ANS = false;
	 	if (!ANS) continue;

	 	string ans = recover_answer(tree);
	 	cout << ans << '\n';
	 	exit(0);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 73ms
memory: 127584kb

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: 89ms
memory: 128208kb

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: 75ms
memory: 128000kb

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: 70ms
memory: 126564kb

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: 93ms
memory: 127380kb

input:

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

output:

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

result:

ok great!!

Test #6:

score: 0
Accepted
time: 88ms
memory: 126536kb

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: 85ms
memory: 126024kb

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: 423ms
memory: 126652kb

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: 207ms
memory: 127812kb

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: 80ms
memory: 127596kb

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:

x+sin(x)

result:

ok great!!

Test #11:

score: 0
Accepted
time: 71ms
memory: 128596kb

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: 82ms
memory: 128472kb

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:

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

result:

ok great!!

Test #13:

score: 0
Accepted
time: 75ms
memory: 127832kb

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: 97ms
memory: 126436kb

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: 86ms
memory: 127800kb

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: 1220ms
memory: 128056kb

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(cos(x))+sin(sin(cos((x)/(x))))

result:

ok great!!

Test #17:

score: 0
Accepted
time: 512ms
memory: 126492kb

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(x)+sin(sin(x+x))))

result:

ok great!!

Test #18:

score: 0
Accepted
time: 152ms
memory: 128964kb

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(x+cos(x-x))))

result:

ok great!!

Test #19:

score: 0
Accepted
time: 59ms
memory: 126288kb

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: 84ms
memory: 126816kb

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:

sin(x-x-x)

result:

ok great!!

Test #21:

score: 0
Accepted
time: 103ms
memory: 126824kb

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: -100
Wrong Answer
time: 79ms
memory: 127712kb

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((x+x)/(x)))

result:

wrong answer div a small number