QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#150738#6395. Equation Discoveringaesthetic#WA 570ms4220kbC++143.2kb2023-08-26 05:33:272023-08-26 05:33:29

Judging History

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

  • [2023-08-26 05:33:29]
  • 评测
  • 测评结果:WA
  • 用时:570ms
  • 内存:4220kb
  • [2023-08-26 05:33:27]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 22;
int n;
double x[MAXN], y[MAXN];

vector<char> ops;

string genExpr(vector<char> ops)
{
	vector<string> a;	
	while(!ops.empty())
	{
		char c = ops.back();
		if(c == 'x')
		{
			a.push_back("x");
		}
		else if(c == '+' || c == '-' || c == '*' || c == '/')
		{
			string z = a.back();
			a.pop_back();
			string w = a.back();
			a.pop_back();
			if(c == '+')
				a.push_back("(" + z + "+" + w + ")");
			else if(c == '-')
				a.push_back("(" + z + "-" + w + ")");
			else if(c == '*')
				a.push_back("(" + z + "*" + w + ")");
			else if(c == '/')
				a.push_back("(" + z + "/" + w + ")");
		}
		else if(c == 's' || c == 'c')
		{
			string z = a.back();
			a.pop_back();
			if(c == 's')
				a.push_back("sin(" + z + ")");
			else if(c == 'c')
				a.push_back("cos(" + z + ")");
		}
		ops.pop_back();
	}
	return a.back();
}

bool getOut(vector<char> ops, double x, double &ret)
{
	vector<double> a;
	while(!ops.empty())
	{
		char c = ops.back();
		if(c == 'x')
		{
			a.push_back(x);
		}
		else if(c == '+' || c == '-' || c == '*' || c == '/')
		{
			if(a.size() < 2)
				return false;
			double z = a.back();
			a.pop_back();
			double w = a.back();
			a.pop_back();
			if(c == '+')
				a.push_back(z + w);
			else if(c == '-')
				a.push_back(z - w);
			else if(c == '*')
				a.push_back(z * w);
			else if(c == '/')
			{
				if(w < 0.001)
					return false;
				a.push_back(z / w);
			}
		}
		else if(c == 's' || c == 'c')
		{
			if(a.size() < 1)
				return false;
			double z = a.back();
			a.pop_back();
			if(c == 's')
				a.push_back(sin(z));
			else if(c == 'c')
				a.push_back(cos(z));
		}
		ops.pop_back();
	}
	if(a.size() != 1)
		return false;
	ret = a.back();
	return true;
}

bool check()
{
	if(ops.empty())
		return false;
	for(int i = 1; i <= n; ++i)
	{
		double yy;
		if(!getOut(ops, x[i], yy))
			return false;
		if(abs(yy - y[i]) >= 1e-5)
			return false;
	}
	return true;
}

bool validatePrefix(vector<char> ops)
{
	int cnt = 0;
	for(int i = 0; i < ops.size(); ++i)
	{
		char c = ops[i];
		if(c == 'x')
			cnt++;
		else if(c == '+' || c == '-' || c == '*' || c == '/')
			cnt--;
		if(cnt > 1)
			return false;
	}

	return true;
}

int cost = 0, xs = 0;
void go()
{
	if(cost > 9 || xs > 5)
		return;

	// cout << "Trying: ";
	// for(char c : ops)
	// 	cout << c << ' ';
	// cout << endl;
	if(!validatePrefix(ops))
		return;

	if(check())
	{
		// for(char c : ops)
		// 	cout << c << ' ';
		// cout << endl;

		cout << genExpr(ops) << endl;
		exit(0);
	}


	for(char c : {'x', '+', '-', '*', 's', 'c', '/'})
	{
		ops.push_back(c);
		if(c == '+' || c == '-' || c == '*' || c == '/')
			cost += 2;
		else if(c == 'c' || c == 's')
			cost++;
		else if(c == 'x')
			xs++;
		go();
		if(c == '+' || c == '-' || c == '*' || c == '/')
			cost -= 2;
		else if(c == 'c' || c == 's')
			cost--;
		else if(c == 'x')
			xs--;
		ops.pop_back();
	}
}


int main()
{
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n;
	for(int i = 1; i <= n; ++i)
		cin >> x[i] >> y[i];
	go();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 127ms
memory: 4020kb

input:

3
1.000000 1.000000
2.000000 4.000000
3.000000 9.000000

output:

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

result:

ok great!!

Test #2:

score: 0
Accepted
time: 123ms
memory: 4220kb

input:

3
0.618000 1.517072
0.314000 3.132637
1.414000 0.494016

output:

(x+((sin(x)/(x*x))-x))

result:

ok great!!

Test #3:

score: 0
Accepted
time: 161ms
memory: 4100kb

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

input:

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

output:


result:

wrong output format Unexpected end of file - token expected