QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#135675#6395. Equation DiscoveringUrgantTeamWA 1380ms160168kbC++236.6kb2023-08-05 21:26:542023-08-05 21:26:55

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-08-05 21:26:55]
  • Judged
  • Verdict: WA
  • Time: 1380ms
  • Memory: 160168kb
  • [2023-08-05 21:26:54]
  • Submitted

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, 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 = 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;
 	}
 	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: 106ms
memory: 159212kb

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

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: 103ms
memory: 158404kb

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: 99ms
memory: 159104kb

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: 99ms
memory: 157144kb

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: 101ms
memory: 159248kb

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: 83ms
memory: 159656kb

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: 479ms
memory: 159632kb

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: 234ms
memory: 157936kb

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: 107ms
memory: 158728kb

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

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: 107ms
memory: 159664kb

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

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

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: 110ms
memory: 157280kb

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: 1380ms
memory: 159392kb

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: 561ms
memory: 158636kb

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: 154ms
memory: 158472kb

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

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:

wrong answer fail to discover