QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#310281#6395. Equation DiscoveringPlentyOfPenalty#WA 78ms74984kbC++202.3kb2024-01-21 10:14:022024-01-21 10:14:02

Judging History

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

  • [2024-01-21 10:14:02]
  • 评测
  • 测评结果:WA
  • 用时:78ms
  • 内存:74984kb
  • [2024-01-21 10:14:02]
  • 提交

answer

#include<bits/stdc++.h>
#define all(x) begin(x),end(x)
#define double long double
using namespace std;
enum oper{PLUS,MINUS,TIME,DIV,SIN,COS,NONE};
string name[]={"+","-","*","/","sin","cos","x"};
const int N=25;
int n;
double x[N],y[N];
double getdiff(double x,double y){
	return abs(x-y)/max<double>(1,abs(y));
}
struct func{
	oper op;
	string str;
	func *l,*r;
	pair<double,bool> calc(double x){
		if(op==NONE)return {x,false};
		if(PLUS<=op&&op<=TIME){
			auto a=l->calc(x),b=r->calc(x);
			if(a.second||b.second){return {0,true};}
			if(op==PLUS)return {a.first+b.first,false};
			if(op==MINUS)return {a.first-b.first,false};
			if(op==TIME)return {a.first*b.first,false};
		}
		if(op==DIV){
			auto a=l->calc(x),b=r->calc(x);
			if(a.second||b.second)return {0,true};
			if(abs(a.first)<=0.015)return {0,true};
			return {a.first/b.first,false};
		}
		if(SIN<=op&&op<=COS){
			auto a=l->calc(x);
			a.first=op==SIN?sinl(a.first):cosl(a.first);
			return a;
		}
		return {0,true};
	}
};
vector<func> f[10];
int main(){
#ifdef memset0
	freopen("B.in","r",stdin);
#endif
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	f[0].push_back({NONE,"x",nullptr,nullptr});
	for(int k=1;k<=9;k++){
		for(oper op=PLUS;op<=DIV;op=(oper)((int)op+1)){
			for(int i=0;i<=k;i++)
				for(int j=0;j<=k;j++)
					if(i+j+2==k){
						// if(op!=MINUS&&op!=DIV&&i>j)continue;
						for(int x=0;x<f[i].size();x++)
							for(int y=0;y<f[j].size();y++){
								f[k].push_back({
									op,
									"("+f[i][x].str+")"+name[op]+"("+f[j][y].str+")",
									&f[i][x],
									&f[j][y],
								});
							}
					}
		}
		for(oper op=SIN;op<=COS;op=(oper)((int)op+1)){
			for(int x=0;x<f[k-1].size();x++){
				f[k].push_back({
					op,
					name[op]+"("+f[k-1][x].str+")",
					&f[k-1][x],
					nullptr
				});
			}
		}
		// cerr<<k<<" >> "<<f[k].size()<<endl;
		// for(auto x:f[k])cerr<<x.str<<endl;
	}
	for(int k=0;k<=9;k++)
		for(auto fc:f[k]){
			bool ok=true;
			for(int i=1;i<=n;i++){
				auto res=fc.calc(x[i]);
				if(res.second||isnan(res.first)||isinf(res.first)||(getdiff(res.first,y[i])>1e-3)){
					ok=false;
					break;
				}
			}
			if(ok){
				// cerr<<"k="<<k<<endl;
				cout<<fc.str<<endl;
				return 0;
			}
		}
	assert(0);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 60ms
memory: 74984kb

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: 78ms
memory: 73684kb

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: 73848kb

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: 78ms
memory: 73664kb

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

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

result:

wrong answer div a small number